并查集

并查集

并查集也称为不相交集数据结构。其目的是找出元素之间的关系并归为若干个集合。

题目示例：

某地的警察发现几条关于犯罪分子的线索，求当地有几个独立的犯罪团伙：

数据给出格式如下：

11 10
1 2
3 4
5 2
4 6
2 6
7 11
8 7
9 7
9 11
1 6

• 第一行两个数字a b，表示有a个犯罪分子和b条线索
• 第二行开始有b行线索，每行两个数字a b，表示a 和 b两个犯罪分子是团伙
• 注意，团伙的团伙也是团伙

利用并查集让团伙的两个犯罪分子”归顺“其中一个，默认右边归顺左边，即靠左原则

解题代码

整体代码

//并查集
#include<iostream>
using namespace std;

int peo, clue;//人数和线索数

int getFather(int* arr,int v)
{
	if (arr[v] == v)
	{
		return v;
		//如果祖先是他自身，则返回
	}
	else
	{
		arr[v] = getFather(arr, arr[v]);
		return arr[v];
		//路径压缩，如果祖先不是自身，则一直找到祖先，然后返回
		//在此过程中对一整条路径进行了压缩
	}
}//寻找祖宗函数

void merge(int* arr, int v, int u)
{
	int t1 = getFather(arr, v);//v的祖宗
	int t2 = getFather(arr, u);//u的祖宗

	if (t1 != t2)
	{
		arr[t2] = t1;
		//这里采用靠左原则，即u归顺v
	}
	return;
}//合并函数

int main()
{
	cin >> peo >> clue;

	int* arr = new int[peo + 1];
	for (int i = 0; i <= peo; i++)
	{
		arr[i] = i;
	}//创建关系数组

	int a, b;
	for (int i = 0; i < clue; i++)
	{
		cin >> a>> b;
		merge(arr, a, b);
	}//输入线索并合并

	int num = 0;
	for (int i = 1; i <= peo; i++)
	{
		if (arr[i] == i)
		{
			num++;
		}
	}

	//输出结果
	cout << "一共有" << num << "个犯罪团伙" << endl;
	cout << "最终数组情况为：" << endl;
	for (int i = 1; i <= peo; i++)
	{
		cout << i << "-" << arr[i] << "  ";
	}

	return 0;
}

核心代码

int getFather(int* arr,int v)
{
	if (arr[v] == v)
	{
		return v;
		//如果祖先是他自身，则返回
	}
	else
	{
		arr[v] = getFather(arr, arr[v]);
		return arr[v];
		//路径压缩，如果祖先不是自身，则一直找到祖先，然后返回
		//在此过程中对一整条路径进行了压缩
	}
}//寻找祖宗函数

void merge(int* arr, int v, int u)
{
	int t1 = getFather(arr, v);//找到v的祖宗
	int t2 = getFather(arr, u);//找到u的祖宗

	if (t1 != t2)
	{
		arr[t2] = t1;
		//这里采用靠左原则，即u归顺v
	}
	return;
}//合并函数

洛谷例题

亲戚

题目背景

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

题目描述

规定：x 和 y 是亲戚，y 和 z 是亲戚，那么 x 和 z 也是亲戚。如果 x，y 是亲戚，那么 x 的亲戚都是 y的亲戚，y的亲戚也都是 x 的亲戚。

输入格式

第一行：三个整数 $n,m,p$，（$n,m,p \le 5000$），分别表示有 $n$ 个人，$m$ 个亲戚关系，询问 $p$ 对亲戚关系。

以下 $m$ 行：每行两个数 $M_i$，$M_j$，$1 \le M_i,~M_j\le N$，表示 $M_i$ 和 $M_j$ 具有亲戚关系。

接下来 $p$ 行：每行两个数 $P_i,P_j$，询问 $P_i$ 和 $P_j$ 是否具有亲戚关系。

输出格式

$p$ 行，每行一个 Yes 或 No。表示第 $i$ 个询问的答案为“具有”或“不具有”亲戚关系。

样例 #1

样例输入 #1

6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6

样例输出 #1

Yes
Yes
No

AC代码

#include<iostream>
using namespace std;

int findFather(int* arr,int v)
{
	if (arr[v] == v)
	{
		return v;
	}
	else
	{
		arr[v] = findFather(arr, arr[v]);
		return arr[v];
	}
}

int main()
{
	int peo, clue, ques;
	cin >> peo >> clue >> ques;
	int* arr = new int[peo + 1];
	int* brr = new int[ques];
	int* crr = new int[ques];
	for (int i = 0; i <= peo; i++)
	{
		arr[i] = i;
	}
    
	int a, b,f1,f2;
	for (int i = 0; i < clue; i++)
	{
		cin >> a >> b;
		f1 = findFather(arr, a);
		f2 = findFather(arr, b);
		if (f1 != f2)
		{
			arr[f2] = f1;
		}
	}
    
	bool ise = false;
	for (int i = 0; i < ques; i++)
	{
		cin >> brr[i] >> crr[i];
	}
	for (int i = 0; i < ques; i++)
	{
		if (ise == false) ise = true;
		else cout << endl;
		arr[brr[i]] = findFather(arr, brr[i]);
		arr[crr[i]] = findFather(arr, crr[i]);
		if (arr[brr[i]] == arr[crr[i]])
		{
			cout << "Yes";
		}
		else
		{
			cout << "No";
		}
	}
	return 0;
}