并查集

一、并查集的定义
图片说明

二、并查集的三个基本操作
图片说明

三、实例分析

1.三个基本操作模板

/*
-------并查集数据结构的实现------
1.makeSet
2.find
3.unionSet

*/

using namespace std;

const int MAXSIZE = 500;
int uset[MAXSIZE];

void makeSet(int size) 
{
	for (int i = 0; i < size; i++) uset[i] = -1;
}

//递归实现
int find_recur(int x) 
{
	if (uset[x] < 0) return x;
	uset[x] = find_recur(uset[x]);
	return uset[x];
}

//非递归实现
int find(int x)
{
	int p = x, t;
	while (uset[p] >= 0) p = uset[p];
	while (x != p) {
		t = uset[x];
		uset[x] = p;
		x = t;
	}
	return x;
}


void unionSet(int x, int y) 
{
	if ((x = find(x)) == (y = find(y))) return;
	if (uset[x] < uset[y]) {
		uset[x] += uset[y];
		uset[y] = x;
	}
	else {
		uset[y] += uset[x];
		uset[x] = y;
	}
}

2.典型应用

（1）亲戚

void test_unionSet01()
{
	int n, m, p;
	cin >> n >> m >> p;
	//初始化并查集
	makeSet(n);
	//根据亲戚关系来合并相应的集合
	while (m--)
	{
		int a, b;
		cin >> a >> b;
		unionSet(a, b);
	}
	//查找是否属于一个集合
	while (p--)
	{
		int a, b;
		cin >> a >> b;
		if (find(a) == find(b))
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}

}

(2) 修路

int father[1005];
int Find(int x)
{

	while (x != father[x])
		x = father[x];
	return x;
}

void Combine(int a, int b)
{
	int fa = Find(a);
	int fb = Find(b);
	if (fa != fb)
	{
		father[fa] = fb;
	}
}

void test_Unioset02()
{
	int n, m;
	int i;
	int a, b;
	while (~scanf("%d", &n))
	{
		if (n == 0)
			break;
		scanf("%d", &m);
		int sum = 0;
		for (i = 1; i <= n; i++)//初始化并查集
			father[i] = i;
		for (i = 0; i<m; i++)//合并
		{
			scanf("%d%d", &a, &b);
			Combine(a, b);
		}
		for (i = 1; i <= n; i++)
		{
			if (father[i] == i)//统计没有被合并的结点个数
				sum++;
		}
		printf("%d\n", sum - 1);//sum个结点之间最少还需要sum - 1条道路
	}

}

（3）数码宝贝

const int N = 100;

int a, b, m, n;             //m, n分别为组数和个数  a, b表示每次在同一个集合的两个数
int father[N];              //集

							//在合并之前初始化每个节点为该集合的根节点(每个数都是一个集合)
void init(int n) {
	for (int i = 1; i <= n; i++) father[i] = i;
}

//找到元素x在该集合中的根节点(根节点满足x == father[x])
int findFather(int x) {     //查
	int a = x;  //记录初始节点
	while (x != father[x]) x = father[x];   //循环结束后的x为该集合的根节点
											//路径压缩，将寻找根节点路途中的每个节点指向其根节点，优化之后的查找速度，可不写
	while (a != father[a]) {
		int b = a;      //记录a，防止后面被覆盖
		a = father[a];  //让a指向其父节点
		father[b] = x;  //指向根节点
	}
	return x;
}

//将a b合并到一个集合中
void Union(int a, int b) {  //并
							//分别找到a, b所在结合的根节点
	int Ra = findFather(a);
	int Rb = findFather(b);
	//当a, b不在同一个集合中时将Ra指向Rb或者将Rb指向Rb指向ba
	if (Ra != Rb) {
		father[Ra] = Rb;    //将Ra指向Rb
							//father[Rb] = Ra; 也可以
	}
}

void UnionSet03()
{
	cin >> n >> m;
	init(n);    //在合并集合之前需初始化，勿遗忘
	while (m--) {
		cin >> a >> b;
		Union(a, b);    //每输入两个数，将其合并到一个集合中
	}
	int ans = 0;    //用来记录集合的个数
					//遍历所有数，根节点的数量即为集合的数量
	for (int i = 1; i <= n; i++) {
		if (i == findFather(i)) ans++;    //i为其所在结合的根节点
	}
	cout << ans << endl;

}

（4）繁华的都市 --- 并查集和最小生成树算法kruskal

int n, m;
int s, maxm;
int p[100002];

struct node {
	int u;
	int v;
	int c;
}info[100002];

bool cmp(node x1, node x2)
{
	if (x1.c != x2.c)return x1.c<x2.c;
	//else if (x1.u != x2.u) return x1.u<x2.u;
	//else return x1.v<x2.v;
}

int find(int x)       //查找x元素所在的集合,回溯时压缩路径
{
	if (x != p[x])
	{
		p[x] = find(p[x]);
	}
	return p[x];
}

void bcj(int x1, int x2)//把x2并入x1的集合
{
	int t1, t2;//存储祖先节点
	t1 = find(x1);
	t2 = find(x2);
	if (t1 != t2)p[t2] = t1;
}

void test_Unioset04()
{
	cin >> n >> m;//n就是顶点数，m是边数
	for (int i = 1; i <= n; i++)//初始化并查集
	{
		p[i] = i;
	}
	for (int i = 0; i<m; i++)
	{
		cin >> info[i].u >> info[i].v >> info[i].c;
	}
	sort(info, info + m, cmp);
	for (int i = 0; i<m; i++)//遍历所有的边
	{
		if (find(info[i].u) != find(info[i].v))
		{
			bcj(info[i].u, info[i].v);//把v并入u的集合
			maxm = max(maxm, info[i].c);
		}
	}
	cout << n - 1 << " " << maxm;

}