先考虑一个联通块，可以发现这个联通快内不会存在两个偶数的点
证明：如果存在，那么这两个点的某一条路径上的边全部反过来，可以使答案+2，即答案为点数或点数-1
同时，发现答案的奇数点数一定与边数同奇偶，那么答案就被确定了，具体实现可以使用并查集
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 200005 4 int n,m,x,y,ans,f[N],e[N],v[N]; 5 int find(int k){ 6 if (k==f[k])return k; 7 return f[k]=find(f[k]); 8 } 9 int main(){ 10 scanf("%d%d",&n,&m); 11 for(int i=1;i<=n;i++)f[i]=i; 12 for(int i=1;i<=n;i++)v[i]=1; 13 for(int i=1;i<=m;i++){ 14 scanf("%d%d",&x,&y); 15 x=find(x); 16 y=find(y); 17 if (x==y)e[x]++; 18 else{ 19 f[x]=y; 20 v[y]+=v[x]; 21 e[y]+=e[x]+1; 22 } 23 } 24 for(int i=1;i<=n;i++) 25 if ((f[i]==i)&&(v[i]%2!=e[i]%2))ans++; 26 printf("%d",n-ans); 27 }
原文：https://www.cnblogs.com/PYWBKTDA/p/11619720.html
