View Code 1 #include2 #include 3 int father[1001]; 4 int find(int x) 5 { 6 if(x!=father[x]) 7 father[x] = find(father[x]); 8 return father[x]; 9 }10 void merge(int x,int y)11 {12 int fx, fy ;13 fx = find(x) ;14 fy = find(y) ;15 if(fx!=fy)16 father[fx] = fy;17 }18 int main()19 {20 int i,n,m,a,b;21 while(scanf("%d",&n)&&n)22 {23 scanf("%d",&m);24 int num = 0;25 for(i = 1 ; i <= n ; i++)26 father[i] = i;27 for(i = 1 ; i <= m ; i++)28 {29 scanf("%d%d",&a,&b);30 merge(a, b) ;31 }32 for(i = 1; i <= n ; i++)33 if(father[i]==i)34 num++;35 printf("%d\n",num-1);36 }37 return 0;38 }
直接套模板，注意题目中从一开始循环
View Code 1 #include2 #include 3 int father[1001] ; 4 int find(int x) 5 { 6 if(x!=father[x]) 7 father[x] = find(father[x]) ; 8 return father[x] ; 9 }10 void merge(int x, int y)11 {12 int fx, fy ;13 fx = find(x) ;14 fy = find(y) ;15 if(fx!=fy)16 father[fx] = fy ;17 }18 int main()19 {20 int n, m, a, b, i;21 while(scanf("%d %d", &n, &m)!=EOF)22 {23 int num = 0 ;24 for(i=1; i<=n; i++)25 father[i] = i ;26 for(i=1; i<=m; i++)27 {28 scanf("%d %d", &a, &b) ;29 merge(a, b) ;30 }31 for(i=1; i<=n; i++)32 if(father[i]==i)33 num++ ;34 printf("%d\n", num) ;35 }36 return 0 ;37 }