题目链接

题目大意

给你一张图,每人可以进行两种操作

  1. 删除一条边

  2. 删除一个无环的连通分量

alice和bob轮流进行,无法删除的人视作败者,求胜者。

解题思路

  1. 边数-1

  2. 等同于删去一棵树,点数-k,边数-(k-1)

任何一种操作都会使得整个图的(点数+边数)减去奇数个,所以答案只和n+m有关。

非常巧妙的一道题,和队友卡了很久。

代码实现

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5+7;
const int eps = 1e-8;
const int inf = 0x7f7f7f7f;
const int mod = 1e9+7;
int T;
int n,m,k;
int a[N];

signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    T=1;
    while(T--){
        cin>>n>>m;
        int u,v;
        for(int i=1;i<=m;i++){
            cin>>u>>v;
        }
        if((n+m)&1){
            cout<<"Alice";
        }
        else{
            cout<<"Bob";
        }
    }
    return 0;
}


0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注