并查集入门与基础应用

并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作。

1. 查询元素a与元素b是否属于同一集合
2. 合并元素a与元素b所在的集合

---

并查集的结构

并查集是由树形结构实现的。每个元素代表一个元素，每个集合代表一棵树。在并查集中通常不过多关心树的形状。

(1)初始化

for (int i = 1; i <= n; i++)
{father[i] = i;
}//用father[]数组存储父节点,初始每个元素独立成树

(2)查询

int find(int x)
{if (father[x] != x)father[x] = find(father[x]);return father[x];
}//这里是压缩路径的递归写法

(3)合并

void join(int a, int b)
{int x1 = find(a);int x2 = find(b);if (x1 != x2)father[x1] = x2;
}//无需在乎树的形状，a、b所在集合合并即可

---

并查集的基础运用

并查集最常用的地方是求无向图的最小生成树

洛谷P3366 【模板】最小生成树

//Kruskal算法
#include <bits/stdc++.h>
#define N 200005
using namespace std;
int n, m, f[N], ans=0;
struct node
{int u, v, w;
} e[N];//记录边的起始、终点和权值
int find(int x)
{if (f[x] == x)return x;return f[x] = find(f[x]);
}
bool cmp(node x, node y)
{return x.w < y.w;
}//按权排序
int main()
{ios::sync_with_stdio(0);cin >> n >> m;for (int i = 1; i <= n; i++)f[i] = i;//初始化for (int i = 0; i < m; i++)cin >> e[i].u >> e[i].v >> e[i].w;sort(e, e + m, cmp);//排序int cnt = 0;for (int i = 0; i < m; i++){int fv = find(e[i].v), fu = find(e[i].u);if (fv == fu)continue;f[fv] = fu;//合并ans += e[i].w;if (++cnt == n - 1)break;//连接的边数为n-1时即可退出，因为树的边数 m = n - 1}cout << ans;return 0;
}

---

种类并查集

由于某些并查集的运用中出现了多种关系，如下题中出现了不同集合间的捕食关系。这时要适当扩大并查集的范围，以存储不同集合间的关系。

洛谷P2024 [NOI2001]食物链

#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
int n, m;
int father[N + 1];
int find(int x)
{if (father[x] != x)father[x] = find(father[x]);return father[x];
}
void join(int a, int b)
{father[find(a)] = find(b);
}
void init()
{for (int i = 1; i <= 3 * n; i++)father[i] = i;//初始化三倍规模的并查集分别存储同类、猎物、天敌
}
int main()
{ios::sync_with_stdio(0);int ans = 0;cin >> n >> m;init();while (m--){int j, a, b;cin >> j >> a >> b;if (a > n || b > n){ans++;continue;}if (j == 1){if (find(a + n) == find(b) || find(a + 2 * n) == find(b))//同类不能捕食或天敌ans++;else{join(a, b);join(a + n, b + n);join(a + 2 * n, b + 2 * n);//同步同类的三种关系}}else{if (a == b)ans++;else{if (find(a + n) == find(b) || find(a) == find(b))//捕食不可逆并且不为同类ans++;else{join(a + n, b + n * 2);join(a + n * 2, b);join(a, b + n);//同步捕食的三种关系}}}}cout << ans;return 0;
}

并查集详解可以参考并查集详解（超级简单有趣~~就学会了）