畅通工程

http://acm.hdu.edu.cn/showproblem.php?pid=1232

View Code

 1 #include <stdio.h>
 2 #include<string.h>
 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 }

直接套模板，注意题目中从一开始循环

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2129

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 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 }