题目大意
给你一张图,每人可以进行两种操作
- 删除一条边
-
删除一个无环的连通分量
alice和bob轮流进行,无法删除的人视作败者,求胜者。
解题思路
- 边数-1
-
等同于删去一棵树,点数-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 条评论