并查集（Disjoint Set）详解+例题

柔情只为你懂 2022-12-17 05:57 84阅读 0赞

**目录**

概述

步骤

例题

题目描述

代码

--------------------

# 概述 #

并查集，顾名思义，需要对集合进行查询与合并。

# 步骤 #

1、初始化：把每个点所在集合初始化为其**自身**；  
2、查询：查询元素所在的集合，即**根节点**；  
3、合并：若集合不同，将两个元素所在的集合合并为一个集合，即**根节点合并**；

并查集是一种树型的数据结构，常常在使用中以森林来表示（可查看[树-双亲表示法][-]）。

合并时有个问题，就是树的深度不要太大，**查询和合并时可以进行路径压缩，一种是低的树合并到高的树，另一种是合并前根的所有子节点的父节点都改为根**。

# 例题 #

来源：[牛客网-KY126 畅通工程][-KY126]

## 题目描述 ##

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

输入描述:

测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。 
        注意:两个城市之间可以有多条道路相通,也就是说
        3 3
        1 2
        1 2
        2 1
        这种输入也是合法的
        当N为0时，输入结束，该用例不被处理。

输出描述:

对每个测试用例，在1行里输出最少还需要建设的道路数目。

示例1

输入

>     4 2
>     1 3
>     4 3
>     3 3
>     1 2
>     1 3
>     2 3
>     5 2
>     1 2
>     3 5
>     999 0
>     0

输出

>     1
>     0
>     2
>     998

## 代码 ##

全局变量

// 父节点 树深度
    int parent[1001];
    int height[1001];

初始化函数，使用height压缩

// 初始化
    void Init(int N)
    {
    	for (int i = 1; i < N + 1; i++)
    	{
    		parent[i] = i;
    		height[i] = 0;
    	}
    }

初始化函数，不使用height压缩

// 初始化
    void Init2(int N)
    {
    	for (int i = 1; i < N + 1; i++)
    	{
    		parent[i] = i;
    	}
    }

查找集合函数

// 查找i所属的集合（根节点）
    int FindRoot(int i)
    {
    	if (parent[i] == i)return i;
    	return FindRoot(parent[i]);
    }

合并集合函数，使用height压缩

// 合并c1，c2所属集合
    void UnionSet(int c1, int c2)
    {
    	int rc1 = FindRoot(c1);
    	int rc2 = FindRoot(c2);
    	if (rc1 != rc2) 
    	{
    		if(height[rc1]<height[rc2])parent[rc1] = rc2;
    		else if(height[rc1]>height[rc2])parent[rc2] = rc1;
    		else
    		{
    			parent[rc2] = rc1;
    			height[rc1]++;
    		}
    	}
    }

路径压缩函数

// 路径压缩，root节点的所有子节点的父节点均为root
    void PathCompression(int root,int p)
    {
    	int tmp = parent[p];
    	while (tmp!=root)
    	{
    		tmp = parent[p];
    		parent[p] = root;
    		p = tmp;
    	}
    }

合并函数，不使用height

// 合并c1，c2所属集合 不使用height
    void UnionSet2(int c1, int c2)
    {
    	int rc1 = FindRoot(c1);
    	int rc2 = FindRoot(c2);
    	PathCompression(rc1,c1);
    	PathCompression(rc2,c2);
    	if (rc1 != rc2)
    	{
    		parent[rc2] = rc1;
    	}
    }

全部代码

/*
    https://www.nowcoder.com/practice/4878e6c6a24e443aac5211d194cf3913?tpId=40&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fkaoyan%2Fquestion-ranking
    Project: KY 126畅通工程
    Date:    2020/10/
    Author:  Frank Yu
    */
    #include<algorithm>
    #include<iostream>
    using namespace std;
    // 父节点 树深度
    int parent[1001];
    int height[1001];
    // 初始化
    void Init(int N)
    {
    	for (int i = 1; i < N + 1; i++)
    	{
    		parent[i] = i;
    		height[i] = 0;
    	}
    }
    // 初始化
    void Init2(int N)
    {
    	for (int i = 1; i < N + 1; i++)
    	{
    		parent[i] = i;
    	}
    }
    // 查找i所属的集合（根节点）
    int FindRoot(int i)
    {
    	if (parent[i] == i)return i;
    	return FindRoot(parent[i]);
    }
    // 合并c1，c2所属集合
    void UnionSet(int c1, int c2)
    {
    	int rc1 = FindRoot(c1);
    	int rc2 = FindRoot(c2);
    	if (rc1 != rc2) 
    	{
    		if(height[rc1]<height[rc2])parent[rc1] = rc2;
    		else if(height[rc1]>height[rc2])parent[rc2] = rc1;
    		else
    		{
    			parent[rc2] = rc1;
    			height[rc1]++;
    		}
    	}
    }
    // 路径压缩，root节点的所有子节点的父节点均为root
    void PathCompression(int root,int p)
    {
    	int tmp = parent[p];
    	while (tmp!=root)
    	{
    		tmp = parent[p];
    		parent[p] = root;
    		p = tmp;
    	}
    }
    // 合并c1，c2所属集合 不使用height
    void UnionSet2(int c1, int c2)
    {
    	int rc1 = FindRoot(c1);
    	int rc2 = FindRoot(c2);
    	PathCompression(rc1,c1);
    	PathCompression(rc2,c2);
    	if (rc1 != rc2)
    	{
    		parent[rc2] = rc1;
    	}
    }
    // 查找集合个数
    int CountRoots(int N)
    {
    	int count = 0;
    	for (int i = 1; i < N + 1; ++i)
    	{
    		if (parent[i] == i)count++;
    	}
    	return count;
    }
    //主函数
    int main()
    {
    	int N, M;
    	while (cin>>N>>M&&N!=0)
    	{
    		// 初始化
    		//Init(N);
    		Init2(N);
    		while(M--)
    		{
    			int c1, c2;
    			cin >> c1 >> c2;
    			//UnionSet(c1, c2);
    			UnionSet2(c1, c2);
    		}
    		int roots = CountRoots(N);
    		cout << roots - 1 << endl;
    	}
    	return 0;
    }

更多数据结构与算法实现：[数据结构（严蔚敏版）与算法的实现（含全部代码）][Link 1]

本人b站账号:[lady\_killer9][lady_killer9]

有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。

[-]: https://blog.csdn.net/lady_killer9/article/details/87925430
[-KY126]: https://www.nowcoder.com/practice/4878e6c6a24e443aac5211d194cf3913?tpId=40&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fkaoyan%2Fquestion-ranking
[Link 1]: https://blog.csdn.net/lady_killer9/article/details/82695895
[lady_killer9]: https://space.bilibili.com/374432302