- #include<stdio.h>
- long long int a[100000],b[100000]={
- 0
- },t=0;
- long long int chazhao(long long int root)
- {
- long long int son,tmp;
- son=root;
- while(root!=a[root])
- {
- root=a[root];
- }
- while(son != root)
- {
- tmp = a[son];
- a[son] = root;
- son = tmp;
- }
- return root;
- }
- int main()
- {
- long long int n,m,i,total,x,y,p,q;
- scanf("%lld %lld",&n,&m);
- total=n-1;
- for(i=1;i<=n;i++)
- a[i]=i;
- for(i=0;i<m;i++)
- {
- scanf("%lld %lld",&q,&p);
- x=chazhao(q);
- y=chazhao(p);
- if(x!=y)
- {
- a[y]=x;
- total--;
- }
- }
- for(i=1;i<=n;i++)
- {
- chazhao(i);
- }
- for(i=1;i<=n;i++)
- {
- b[a[i]]++;
- }
- for(i=1;i<=n;i++)
- if(b[i]!=0)
- t++;
- printf("%lld",t);
- return 0;
- }(大概就这样, emmm, 很好理解应该)
来源: http://www.bubuko.com/infodetail-3392965.html