背景描述： 不是一切深渊都是灭亡 不是一切灭亡都覆盖在弱者的头上 ——《这也是一切》 舒婷 有N个透明的盒子， 每个盒子里面有两个不同颜色的球， 总共有M种颜色。 Alice和Bob又在玩游戏， 具体的， Alice会从N个盒子里面选出若干个， Bob再从Alice选出的盒子里面选出一些（不能不选）， 如果在Bob选出的盒子中， 每个颜色的球都总共出现了偶数次（0次也是偶数次）， 那么Bob胜利， 否则Alice胜利 在Alice和Bob都足够聪明的情况下， Alice想知道自己在能够获胜的前提下， 第一次最多可以选出几个盒子 输入格式： 第一行有两个整数N和M， 意义如题 接下来N行， 第i+1行两个整数表示第i+1个盒子里面的两个球分别是什么颜色的 输出格式： 一行一个整数表示Alice最多可以选多少个盒子 样例输入： 3 3 1 2 2 3 2 3 样例输出： 2 数据规模： 对于30%的数据， N <= 10 对于50%的数据， N <= 20 对于100%的数据， N <= 100000， M <= 2N
我们把每一个颜色当成点，盒子当成线，建一个图。对于每不合法一个小块修改为一颗树。见图。 这是一个合法的图。 这是一个不合法的图，我们把它修改为上图。
最后对于每一块都是点数减一，统计总数。
附程序：
//把颜色当点，盒子当边，然后对于每一个小块修改为一棵树。 //不是一切深渊都是灭亡 //不是一切灭亡都覆盖在弱者的头上 #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<vector> #include<queue> #include<stack> #include<map> #include<set> #include<string> #include<iomanip> #include<ctime> #include<climits> #include<cctype> #include<algorithm> #define clr(a,x) memset(x,a,sizeof(x)) #define ll long long #ifdef WIN32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; const int maxm = 2e5+5; int n,m,a,b,be[maxm],tot,num[maxm],ans; struct Edge { int from,to; int belong; }edge[maxm]; vector<int> g[maxm]; template <class T> inline void read(T &xx) { xx = 0; T flag = 1; char ch = (char)getchar(); while(ch<'0' || ch>'9') { if(ch == '-') flag = -1; ch = (char)getchar(); } while(ch>='0' && ch<='9') { xx = (xx<<1) + (xx<<3) + ch - '0'; ch = (char)getchar(); } xx *= flag; } void dfs(int s) { for(int i = 0; i < g[s].size(); i++) { int v = g[s][i]; if(!be[v]) { be[v] = be[s]; dfs(v); } } } int main() { freopen("heart.in","r",stdin); freopen("heart.out","w",stdout); read(n); read(m); for (int i = 1; i <= n; i++) { read(a); read(b); g[a].push_back(b); g[b].push_back(a); edge[i].to = a; edge[i].from = b; } for (int i = 1; i <= m; i++) { if(!be[i]) be[i] = ++tot; dfs(i); } for (int i = 1; i <= m; i++) num[be[i]]++; for (int i = 1; i <= tot; i++) ans += num[i] - 1; printf("%d",ans); return 0; }