HDU1232 畅通工程

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int pre[1005];　　//存储前驱结点
 5 
 6 void init(int n)　　//对n个结点初始化
 7 {
 8     for(int i = 1; i <= n; i++)
 9         pre[i] = i;　　//让每个结点的根节点为自己，即各自是一个独立的节点
10 }
11 
12 int find(int x)　　//寻找当前结点的根节点
13 {
14     while(x != pre[x])
15         x = pre[x];
16     
17     return x;
18 }
19 
20 void judge(int fx, int fy)　　//判断两个结点是为具有一个根节点
21 {
22     if(fx != fy)　　//如果两个结点的根节点不同则归入合并
23         pre[fx] = fy;
24 }
25 
26 int main()
27 {
28     int n, m, x, y, fx, fy;
29     while(scanf("%d",&n) != EOF && n)
30     {
31         scanf("%d", &m);
32         int cnt = n - 1;　　//n个结点要连通有n-1条待修的路
33         init(n);
34         for(int i = 0; i < m; i++)
35         {
36             scanf("%d%d", &x, &y);
37             fx=find(x);
38             fy=find(y);
39             judge(fx, fy);
40         }
41         for(int i = 1; i <= n; i++)
42         {
43             if(pre[i] != i)　　//如果当前节点不是根节点则此路已修过
44                 cnt--;
45         }
46         printf("%d\n",cnt);
47     }
48     return 0;
49 }