并 查 集

1.双亲表示法

根节点可以为自己，也可以为-1 

2.并查集的概念 

在有些问题中，我们需要维护若⼲个集合，并且基于这些集合要频繁执⾏下⾯的操作：

• 查询操作：查找元素 属于哪⼀个集合。⼀般会在每个集合中选取⼀个元素作为代表，查询的是 这个集合中的代表元素；

x

• 合并操作：将元素 所在的集合与元素所在的集合合并成⼀个集合；（注意，合并的是元素所 在的集合，不是这两个元素！）

x y

• 判断操作：判断元素x 和y 是否在同⼀个集合。

find操作：从当前节点频繁进行找父亲的操作，一直找到根节点，就可以找到代表集合的代表元素了

union:找到该树的根节点，在把这个根节点挂在另一棵树的后边，变成子树即可。修改该根节点的父亲

is same:找两个节点的父亲是否相同

3.并查集的实现 

3.1初始化

初始状态下，所有的元素单独成为⼀个集合：

• 让元素⾃⼰指向⾃⼰即可。

const int N = 1e6 + 10;

int n;

int fa[N]; // 双亲表⽰法所需的数组 

// 初始化并查集 

void init()
{
 for(int i = 1; i <= n; i++) fa[i] = i;
}

3.2 查询操作

查询操作是并查集的核⼼操作，其余所有的操作都是基于查询操作实现的！ 找到元素x 所属的集合：

• ⼀直向上找爸爸~

// 查询操作 

int find(int x)
{
 if(fa[x] == x) return x;
 return find(fa[x]);
 
 // ⼀⾏实现 
 return fa[x] == x ? x : find(fa[x]);
}

3.3 合并操作

将元素x 所在的集合与元素y 所在的集合合并成⼀个集合：

• 让元素x 所在树的根节点指向元素y 所在树的根节点。反过来也是可以的）

// 合并操作 

void un(int x, int y) // 注意，函数名字不能⽤ union，因为它是 C++ 的关键字 
{
 int fx = find(x);
 int fy = find(y);
 fa[fx] = fy;
}

3.4 判断操作

// 判断是否在同⼀集合 

bool issame(int x, int y)
{
 return find(x) == find(y);
}

3.5 并查集的优化

极端情况：在合并的过程中，整棵树变成⼀个链表。 路径压缩：在查询时，把被查询的节点到根节点的路径上的所有节点的⽗节点设置为根节点，从⽽减 ⼩树的深度。也就是说，在向上查询的同时，把在路径上的每个节点都直接连接到根上，以后查询时 就能直接查询到根节点。

// 找根节点 - 路径压缩 

int find(int x)
{
 if(fa[x] == x) return x;
 return fa[x] = find(fa[x]);
 
 // ⼀⾏实现 
 return fa[x] == x ? x : fa[x] = find(fa[x]);
}

题目： 

1.P3367 【模板】并查集 - 洛谷

#include<iostream>

using namespace std;
const int N = 2e5 + 10;
int n, m;
int f[N];

//查找
int find(int x)
{
	if (f[x] == x)return x;//如果是根节点的话，就返回x
	return  f[x] = find(f[x]);//find(f[x])继续返回父节点直到是根节点为止，f[x] = find(f[x])路径压缩
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)f[i] = i;
	while (m--)//合并
	{
		int z, x, y; cin >> z >> x >> y;
		if (z == 1)
		{
			//找两个的父节点
			int fx = find(x);
			int fy = find(y);
			f[fy] = fx;//把一个的父节点设置成另一个
		}
		else
		{
			if (find(x) == find(y))cout << "Y" << endl;//判断是否相等
			else cout << "N" << endl;
		}
	}
}

2.P1551 亲戚 - 洛谷

#include<iostream>

using namespace std;

const int N = 5e3 + 10;
int f[N];
int n, m, p;

int find(int x)
{
	if (f[x] == x)return x;
	return f[x] = find(f[x]);
}

int main()
{
	cin >> n >> m >> p;
	for (int i = 1; i <= n; i++)f[i] = i;//初始化
	while (m--)
	{
		int x, y; cin >> x >> y;
		int fx = find(x);
		int fy = find(y);
		f[fx] = fy;
	}
	while (p--)
	{
		int x, y; cin >> x >> y;
		if (find(x) == find(y))cout << "Yes" << endl;
		else cout << "No" << endl;
	}
}

3.P1596 [USACO10OCT] Lake Counting S - 洛谷

#include<iostream>

using namespace std;
int n, m;
const int N = 110;
int f[N * N];//记录父节点
char a[N][N];//记录数据

int dx[] = { 1,1,1,0,-1 };
int dy[] = { -1,0,1,1,1 };

int find(int x)
{
	if (f[x] == x)return x;
	return f[x] = find(f[x]);
}

void uni(int pos1, int pos2)
{
	int f1 = find(pos1);
	int f2 = find(pos2);
	f[f1] = f2;
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)//根基八数码问题，下标从0开始计算，才可以符合条件
	{
		for (int j = 0; j < m; j++)
		{
			cin >> a[i][j];
		}
	}
	for (int i = 0; i < m * n; i++)f[i] = i;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (a[i][j] == '.')continue;
			int pos = i * m + j;
			for (int k = 0; k < 5; k++)
			{
				int x = i + dx[k];
				int y = j + dy[k];
				if (x >= 0 && x < n && y >= 0 && y < m && a[x][y] == 'W')
				{
					uni(pos, x * m + y);
				}
			}
		}
	}
	int ret = 0;
	//判断有多少个节点的f[pos] = pos;
	for (int i = 0; i < m * n; i++)
	{
		int x = i / m;
		int y = i % m;
		if (a[x][y] == 'W' && f[i] == i)ret++;
	}
	cout << ret << endl;
}

 4.P1955 [NOI2015] 程序自动分析 - 洛谷

 

#include<iostream>
#include<unordered_map>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
//并查集
LL f[N * 2];
//找
int find(int x)
{
	if (f[x] == x)return x;
	return f[x] = find(f[x]);
}
//并
void un(int x, int y)
{
	int fx = find(x);
	int fy = find(y);
	f[fx] = fy;
}
//判
bool issame(int x, int y)
{
	return find(x) == find(y);
}

//离散化
int pos = 0;
LL dis[N * 2];//排序后的数据
unordered_map<LL, LL> map;//元素，转化后的序号


//
int t, n;
struct node
{
	LL x;
	LL y;
	LL e;
}h[N*2];


bool solve()
{
	cin >> n;
	int pos = 0;//清空数组
	map.clear();

	for (int i = 1; i <= n; i++)//输入数据
	{
		cin >> h[i].x >> h[i].y >> h[i].e;
		dis[++pos] = h[i].x; dis[++pos] = h[i].y;
	}
	//排序
	sort(dis + 1, dis + 1 + pos);
	//离散化
	int cnt = 0;
	for (int i = 1; i <= pos; i++)
	{
		if (map.count(dis[i]))continue;
		map[dis[i]] = ++cnt;
	}
	for (int i = 1; i <= cnt; i++)f[i] = i;//对并查集进行排序
	//先对相等的进行组合
	for (int i = 1; i <= n; i++)
	{
		int x = h[i].x, y = h[i].y;
		if (h[i].e == 1)
		{
			un(map[x], map[y]);
		}
	}
	//在对不等的尽心判断
	for (int i = 1; i <= n; i++)
	{
		int x = h[i].x, y = h[i].y;
		if (h[i].e == 0)
		{
			if(issame(map[x],map[y]))return false;
		}
	}
	return true;
}

int main()
{
	cin >> t;
	while (t--)
	{
		if (solve())cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}