[noi712]练级

先考虑一个联通块，可以发现这个联通快内不会存在两个偶数的点
证明：如果存在，那么这两个点的某一条路径上的边全部反过来，可以使答案+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 }

巴特西

[noi712]练级

最新文章

热门文章