http://acm.hdu.edu.cn/showproblem.php?pid=1213
和畅通工程是一个意思、、
View Code
#include <stdio.h> #include <string.h> #include <stdlib.h> int idx[2000]; int n,m; int find(int x) { //找x所在并查集的根节点 return idx[x]==x?x:idx[x]=find(idx[x]); } int add(int a,int b) { //把b连到a上 return idx[b]=a; } int main() { int a,b,i; int p,q; int ans; int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); ans=n-1; for(i=1;i<=n;i++) idx[i]=i; for(i=0;i<m;i++) { scanf("%d%d",&a,&b); p=find(a); q=find(b); if(p!=q) { add(p,q); ans--; } } printf("%d\n",ans+1); } return 0; }