hdu1232 畅通工程【并查集】超详细题解

约定不等于承诺〃 2021-07-24 21:08 422阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.题意
         *  3.思路
         *  4.代码

### 1.题目 ###

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？  
Input  
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。  
注意:两个城市之间可以有多条道路相通,也就是说  
3 3  
1 2  
1 2  
2 1  
这种输入也是合法的  
当N为0时，输入结束，该用例不被处理。  
Output  
对每个测试用例，在1行里输出最少还需要建设的道路数目。  
Sample Input  
4 2  
1 3  
4 3  
3 3  
1 2  
1 3  
2 3  
5 2  
1 2  
3 5  
999 0  
0  
Sample Output  
1  
0  
2  
998

### 2.题意 ###

使全省任何两个城镇间都可以实现交通，最少还需要建设多少条道路？

### 3.思路 ###

并查集的经典题目。关于并查集的最好学习：[点击这里][Link 1].  
连通n个点最少需要n-1条边，相互连接的城市构成一个集合，只需要判断集合个数即可知道要修多少条路，集合个数的判断也可以根据每个集合只有一个根节点的特征，找n个数里有几个根节点，并减去1，就是答案。

### 4.代码 ###

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn = 5005;
    int Fa[maxn],Rank[maxn];
    void init(int n)  ///初始化
    { 
    	for (int i = 1; i <= n; i++)
    	{ 
    		Fa[i] = i;
    		Rank[i] = 1;
    	}
    }
    int find(int x) //查找
    { 
    	return x == Fa[x]? x:(Fa[x] = find(Fa[x]));//路径压缩
    }
     void merge(int i, int j) //合并
    { 
    	 int x = find(i), y = find(j);
    	 if (Rank[x] <= Rank[y])
    	 { 
    		 Fa[x] = y;
    	 }
    	 else
    	 { 
    		 Fa[y] = x;
    	 }
    	 if (Rank[x] == Rank[y] && x!=y)
    	 { 
    		 Rank[y]++;
    	 }
    }
    
    int main()
    { 
    
    	int n, m;
    	while (cin >> n && n)
    	{ 
    		cin >> m;
    		init(n);  ///初始化
    		int x, y;
    		for (int i = 1; i <= m; i++)
    		{ 
    			cin >> x >> y;
    			merge(x, y); //合并
    		}
    		int cnt = 0;
    		for (int i = 1; i <= n; i++)  //统计共有几个根节点
    		{ 
    			if (Fa[i] == i)
    			{ 
    				cnt++;
    			}
    		}
    		cout << cnt - 1 << endl; //根节点的个数-1即为答案。
    	}
    	return 0;
    }

[Link 1]: https://zhuanlan.zhihu.com/p/93647900