Skip to main content

并查集

参考资料​

简介​

并查集（Disjoint Set Union，DSU）维护若干不相交集合，支持合并两个集合、查询元素所属集合两种操作。每个集合用一棵树表示，根作为代表元，find 沿父指针上溯到根。配合 路径压缩（查询时把路径上的点直接挂到根）与 按秩合并，单次操作的均摊复杂度为反阿克曼函数 O(α(n))O(\alpha(n))，近似常数。

实现​

229 Bcpp
struct DSU
{
	int fa[N];
	void init(int n){for(int i=1;i<=n;i++)fa[i]=i;}
	int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
	void merge(int u,int v){fa[find(u)]=find(v);}
	bool query(int u,int v){return find(u)==find(v);}
};

例题​

洛谷 P3367 【模板】并查集

如题，现在有一个并查集，你需要完成合并和查询操作。

洛谷 P1525 [NOIP 2010 提高组] 关押罪犯

有 nn 个点和 mm 条带权边。将所有点分入两个集合，使两端处于同一集合的边的最大边权尽量小，求这个最小值。

洛谷 P1892 [BalticOI 2003] 团伙

现在有 nn 个人，他们之间有两种关系：朋友和敌人。我们知道：

  • 一个人的朋友的朋友是朋友
  • 一个人的敌人的敌人是朋友

现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。

洛谷 P2024 [NOI2001] 食物链

有 NN 个动物，每个属于 A,B,CA,B,C 之一，且 AA 吃 BB、BB 吃 CC、CC 吃 AA。给出 KK 句话，1 X Y 表示 X,YX,Y 同类，2 X Y 表示 XX 吃 YY。一句话与已有真话矛盾、或 X,Y>NX,Y>N、或称 XX 吃 XX 时即为假话。求假话的总数。