一篇并查集代码模板及经典例题

Myth丶恋晨 2023-02-13 03:50 35阅读 0赞

#### 一、定义 ####

**并查集**就是对集合进行合并及查询，包括两部分，**并（union）和查（find）**。 “并”是将有关联的元素合并为一个集合，“查”是查找这个元素属于哪个集合。

**路径压缩**：为了加快查找速度，查找时将x到根节点路径上的所有点的祖先设为根节点，该优化方法称为压缩路径  
如从属关系A -> B -> C -> D，我们可以直接记A ->D，B -> D，C -> D，D -> D，即加快了从A访问祖先的速度。  
![路径压缩示例][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70]

#### 二、万能模板 ####

#include<iostream>
    #include<vector>
    
    using namespace std;
    int n;
    vector<int> father;
    
    int find_loop(int n)	//循环，非递归
    { 
    	while(n != father[n])
    		n = father[n];
    	return n;
    }
    int find(int n)		//递归型
    { 
    	if(father[n] == n)
    		return n;
    	return find(father[n]);
    }
    
    int Find(int n)		//路径压缩型
    { 
    	if(father[n] == n)
    		return n;
    	father[n] = Find(father[n]);	//直接将n的祖先指到根部
    	return father[n];
    }
    
    void Union(int a,int b)		//集合，默认将a的祖先变为b的祖先
    { 
    	int fa = find(a);
    	int fb = find(b);
    	father[fb] = fa;
    }
    
    int main()
    { 
    	cin >> n;
    	for(int i = 0;i < n;i++)
    		father.push_back(i);	//初始化，最初将所有人的祖先定义为自己
    
    	return 0;
    }

#### 三、用途 ####

1.集合划分问题  
2.领导关系、从属关系的判断  
3.判断加一条边是否产生环  
4.计算子图的数量

#### 四、经典例题 ####

1.[P1551 亲戚][P1551]  
思路：很基础的并查集模板题，将有亲戚关系的人放在一个集合中，然后据题检查要判断的两个人的祖先是否相同即可。

#include<iostream>
    #include<vector>
    
    using namespace std;
    int n,m,p;
    vector<int> father;
    
    int Find(int n)
    { 
    	if(father[n] == n)
    		return n;
    	father[n] = Find(father[n]);
    	return father[n];
    }
    
    void Union(int a,int b)
    { 
    	int fa = Find(a);
    	int fb = Find(b);
    	father[fb] = fa;
    }
    
    int main()
    { 
    	int a,b;
    	cin >> n >> m >> p;
    	for(int i = 0;i < n;i++)
    		father.push_back(i);	//初始化
    
    	for(int i = 0;i < m;i++)
    	{ 
    		cin >> a >> b;
    		Union(a,b);	//合并
    	}
    	
    	for(int i = 0;i < p;i++)
    	{ 
    		cin >> a >> b;
    		if(Find(a) == Find(b)	//查找
    			cout << "Yes";
    		else
    			cout << "No";
    	}
    
    	return 0;
    }

2.[P1536 村村通][P1536]  
思路:将相通的村子划成一个集合，然后只需修路将各集合连接起来即可实现所有村子互通，所以修路数为集合数减1 。

#include<iostream>
    #include<vector>
    
    using namespace std;
    int n,m;
    vector<int> father;
    
    int Find(int n)
    { 
    	if(father[n] == n)
    		return n;
    	father[n] = Find(father[n]);
    	return father[n];
    }
    
    void Union(int a,int b)
    { 
    	int fa = Find(a);
    	int fb = Find(b);
    	father[fb] = fa;
    }
    
    int main()
    { 
    	int a,b;
    	while(cin >> n && n && cin >> m)
    	{ 
    		int cnt = 0;
    		father.clear();
    		for(int i = 0;i <= n;i++)
    			father.push_back(i);	//初始化
    		for(int i = 0;i < m;i++)
    		{ 
    			cin >> a >> b;
    			Union(a,b);	//合并
    		}
    		for(int i = 1;i <= n;i++)
    			if(Find(i) == i)	//查找
    				cnt++;
    
    		if(cnt)
    			cnt--;
    		cout << cnt << endl;
    	}
    	
    	return 0;
    }

3.[200 岛屿数量][200]  
题目大意：给定一个n行m列的海图，1代表陆地，0代表大海，所有上下左右相连的陆地称为同一个岛屿（斜向不算），求此海图的岛屿数量

思路：此题用dfs染色法可以解决，详见[另一篇文章][Link 1]。但此处也可以用并查集解决，将所有连着的陆地合并成一个集合，然后只需要检查有多少个集合即可。但是问题来了，如何把二维的地图转换成一维的father数组呢，就只能用拼接的办法来将二维拼成一维的。例如mp\[i\]\[j\]可以看成father\[i\*m+j\]。

#include<iostream>
    #include<vector>
    
    using namespace std;
    const int N = 110;
    vector<int> father;
    int n, m,cnt,mp[N][N];
    int direction[4][2] = { { 0,1},{ 1,0},{ -1,0},{ 0,-1}};
    
    int Find(int n)
    { 
    	if(father[n] == n)
    		return n;
    	father[n] = Find(father[n]);
    	return father[n];
    }
    
    void Union(int a,int b)
    { 
    	int fa = Find(a);
    	int fb = Find(b);
    	father[fb] = fa;
    }
    
    int main()
    { 
    	cin >> n >> m;
    	for(int i = 0;i < n*m;i++)
    		father.push_back(i);	//初始化
    	for(int i = 0;i < n;i++)
    		for(int j = 0;j < m;j++)
    			cin >> mp[i][j];
    			
    	for(int i = 0;i < n;i++)
    		for(int j = 0;j < m;j++)
    			if(mp[i][j] == 1)	//如果是陆地
    				for(int k = 0;k < 4;k++)	//上下左右扩展
    				{ 
    					int tx = i + direction[k][0];
    					int ty = j + direction[k][1];
    					if(mp[tx][ty] == 1 && tx >= 0 && ty >= 0 && tx < n && ty < m)	//扩展的点也是陆地且在地图内
    						Union(i*m+j,tx*m+ty);	//合并
    				}
    	
    	for(int i = 0;i < n;i++)
    		for(int j = 0;j < m;j++)
    			if(mp[i][j] == 1)
    				if(Find(i*m+j) == i*m+j)	//查找
    					cnt++;
    	cout << cnt << endl;
    
    	return 0;
    }

4.[冗余连接][Link 2]  
题目大意：对一个有n个顶点的无环无向图进行加边操作，若加的边构成了一个环，则返回这条边。若有多个答案，返回最后一条边。

思路：用并查集判断连通性，加边前进行判断，若这两个顶点已属于一个集合，则加此边后就会构成环；若这两个点不属于同一个集合，则加边后会连通，不会成环，再将这两个点合并为同一个集合。

#include<iostream>
    #include<vector>
    
    using namespace std;
    vector<int> father;
    int n,m,ansa,ansb;
    
    int Find(int n)
    { 
    	if(father[n] == n)
    		return n;
    	father[n] = Find(father[n]);
    	return father[n];
    }
    
    bool Union(int a,int b)
    { 
    	int fa = Find(a);
    	int fb = Find(b);
    	father[fb] = fa;
    	return (fa == fb);	//fa == fb代表a和b是同一个祖先，即在一个集合中
    }
    
    int main()
    { 
    	int a,b;
    	cin >> n >> m;		//n个顶点，m条边
    	for(int i = 0;i < n;i++)
    		father.push_back(i);	//初始化
    	for(int i = 0;i < m;i++)
    	{ 
    		cin >> a >> b;
    		if(Union(a,b))		//合并
    			ansa = a,ansb = b;
    	}
    
    	cout << ansa << " " << ansb;
    
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200604165704677.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx,size_16,color_FFFFFF,t_70
[P1551]: https://www.luogu.com.cn/problem/P1551
[P1536]: https://www.luogu.com.cn/problem/P1536
[200]: https://leetcode-cn.com/problems/number-of-islands/
[Link 1]: https://blog.csdn.net/qq_45735851/article/details/105447364
[Link 2]: https://leetcode-cn.com/problems/redundant-connection/