数据结构实验9：并查集的使用

问题描述：
给定一个图，图中有N个顶点(1<=N<=500)，编号依次为1,2,3,⋯⋯,□( ) N。部分顶点之间存在一条无向边。请找出图中所有的极大连通子图。其中，极大联通子图可以描述为该子图中任意两个顶点之间都存在一条路径，且加入任何一个不在该子图的顶点都会导致它不再连通。

输入：第一行为两个数N和M。其中，N 表示顶点的个数，且1<=N<=500，M表示接着有M行的输入数据。这M行数据中，每行包含两个整数P1和P2，表示P1与P2之间存在一条边。
输出：所有的极大联通子图。

输入样例：
6 5
1 2
2 3
3 1
4 5
5 6
输出样例：
1 2 3
4 5 6

相关网站：
http://poj.org/problem?id=1611
http://poj.org/problem?id=1182

解题过程：
既然已经知道这道题要用并查集来做，先去了解一下什么是并查集
力扣547：省份数量
可以通过做这道题，来掌握并查集的基本 *** 作。

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

并查集：
并union 合并具有共同祖先的节点
查：查找节点的祖先
集：通过哈希集合的形式来保存节点之间的关系

1.添加
添加很简单，哈希表一一对应即可，由于刚开始不知道节点之间对应关系，所以初始父节点都设为-1,添加前检测是否已经存在了。

class UnionFindSet
{
private:
	unordered_map<int,int>set;
public:
	void add(int x){
		if(!set.count(x)){
			set[x] = -1;
		}
	}
}

以上是初步的结果，节点的添加需要考虑相互之间的关系，这个在接下来的合并中进行处理。
2.查找祖先
输入的图各个节点之间的关系往往是错综复杂的，这个关系在输入的时候一般都会明确的给出，查找祖先就是把一个连通子图的祖先给找到，从而之后可以用这个来判断两个节点是否在一个子图里.
具体过程就是，之前设置的父节点都是-1，意味着父节点不是-1的都需要往上找，循环给哈希表赋值即可。

class UnionFindSet
{
private:
	unordered_map<int,int>set;
public:
	void add(int x){
		if(!set.count(x)){
			set[x] = -1;
		}
	}
	int find(int x){
		while(set[x] != -1){
			x = set[x];
		}
		return x;
	}
}

路径压缩的思想
我们在判断两个节点是否在同一个连通分量，只需要比较祖先节点是否相同，具体路径不需要考虑
就是可以把
1
2
3
4
5
简化成
1
2 3 4 5
之后查找就方便了

class UnionFindSet
{
private:
	unordered_map<int,int>set;
public:
	void add(int x){
		if(!set.count(x)){
			set[x] = -1;
		}
	}
	int find(int x){
		int root = x;
		while(set[root] != -1){
			root = set[root];
		}
		while(set[x] != -1){
			int temp = set[x];
			set[x] = root;
		}
		return x;
	}
}

3.判断两个节点是否连通，连通的需要合并
具体 *** 作是看是否有共同祖先，有共同祖先的把其中之一的祖先节点的父节点设置为另一个节点的祖先节点

class UnionFindSet
{
private:
	unordered_map<int,int>set;
public:
	void add(int x){
		if(!set.count(x)){
			set[x] = -1;
		}
	}
	int find(int x){
		int root = x;
		while(set[root] != -1){
			root = set[root];
		}
		while(set[x] != -1){
			int temp = set[x];
			set[x] = root;
		}
		return x;
	}
	bool isConnected(int x1,int x2){
		//调用find函数
		if(find(x1) == find(x2)){
			return true;
		}
		else return false;
	}
	void merge(int x1,int x2){
		if(isConnected(x1,x2)){
			int root1 = find(x1);
			int root2 = find(x2);
			set[root1] = root2;
		}
	}
}

未完待续……………

第一次做老是错，以为是find函数问题，最后发现是for循环的问题，之前为了1-n对应，把for循环改成1-n，发现数组下标溢出，只把<=n改了，没改从1开始。

改过来直接通过了
所以模板是没有问题的

然后来看这个题：与省份问题不同的是，省份问题只统计连通子图数量，而本题需要分开输出连通子图每一个节点。
这里我们采用一个比较麻烦的方式来遍历输出
1.先找到根节点，根节点是父节点为-1的节点
2.遍历找到祖先节点是根节点的节点

	void printAns(int n) {
		for (int i = 1; i <= n; i++) {
			if (set[i] == -1) {
				int root = i;
				for (int j = 1; j <= n; j++) {
					if (find_zip(j) == root) {
						cout << j << "	";
					}
				}
			}
			cout << endl;
		}
	}

完整代码

#include 
#include 
using namespace std;

class UnionFindSet 
{
private:
	unordered_map<int, int>set;
public:
	void add(int x) {
		if (!set.count(x)) {
			set[x] = -1;//仅仅是加入了并查集，前后关系还不知道
		}
	}

	int find_zip(int x) {
		int root = x;
		while (set[root] != -1) {
			root = set[root];
		}
		while (set[x] != -1) {
			int temp = set[x];
			set[x] = root;
			x = temp;
		}
		return root;
	}

	void unionNode(int n1,int n2) {
		int root1 = find_zip(n1);
		int root2 = find_zip(n2);
		if (root1 != root2) {
			set[root1] = root2;
		}
	}

	void print(int n) {
		for (int i = 1; i <= n; i++) {
			cout << set[i] << "	";
		}
		cout << endl;
	}
	void printAns(int n) {
		for (int i = 1; i <= n; i++) {
			if (set[i] == -1) {
				int root = i;
				for (int j = 1; j <= n; j++) {
					if (find_zip(j) == root) {
						cout << j << "	";
					}
				}
			}
			cout << endl;
		}
	}
};
int main() {
	UnionFindSet ufs;
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		ufs.add(i);
	}
	int node1, node2;
	for(int i = 0; i < m;i++) {
		cin >> node1 >> node2;
		ufs.unionNode(node1, node2);
	}
	ufs.print(n);
	//找-1.。。
	ufs.printAns(n);
}

其他的题还有
ACM 1611
ACM 1182
以后再看吧。