并查集基础
并查集（\(\sf Disjoint \ Set \ Union\)，\(\sf DSU\)）是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。
-
初始化：
初始化时每个节点均为一个集合，因此根节点初始化为自己。
for (int i = 1; i <= n; i++) fa[i] = i; -
查询：
我们只需要不断向上走就能找到祖宗节点，但是如果是一条链复杂度就会高达 \(O(n)\)，我们可以采用一种路径压缩的方式，我们需要维护的是集合，并不会在意节点的父亲，我们只需要知道祖先即可，于是当我们找到一个节点的祖宗后，直接让节点指向祖宗。这样做的时间复杂度约为 \(O(\alpha(n))\)，可以认为是 \(O(1)\) 的。
int find(int x) { if (x == fa[x]) return x; return fa[x] = find(fa[x]); // 路径压缩 } -
合并：
让一个节点的祖宗指向另一个节点的祖宗即可。有一种按秩合并的优化方法，用处不大。
void merge(int x, int y) { int xx = find(x), yy = find(y); if (xx != yy) fa[xx] = yy; }
以上就是并查集的基础操作。模板：
struct DSU {
vector<int> f, siz;
DSU() {}
DSU(int n) {
init(n);
}
void init(int n) {
f.resize(n + 1);
iota(f.begin(), f.end(), 0);
siz.assign(n + 1, 1);
}
int find(int x) {
if (x == f[x]) return x;
return f[x] = find(f[x]);
}
bool query(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) {
return false;
} else {
f[x] = y;
siz[y] += siz[x];
return true;
}
}
int size(int x) {
return siz[find(x)];
}
int block(int n) {
int ans = 0;
for (int i = 1; i <= n; i++) {
if (i == find(i)) {
ans++;
}
}
return ans;
}
};
进阶并查集
带点权的并查集：
设 \(w[x]\) 表示 \(x\) 的点权，当合并时 \(\tt w[y] += w[x]\)。
带边权的并查集：
原来的并查集功能很单调，实际上我们还可以利用并查集维护更多的信息，就比如：边权。在下面中，我们用 \(w[x]\) 表示 \(x \to root\) 的权值。
-
路径压缩
路径压缩时，我们需要先记录下 \(f_x\) 的值，在回溯的时候 \(w[x]\) 加上 \(w[f_x]\)，如：
int find(int x) { if (x == f[x]) { return x; } else { int ret = f[x]; f[x] = find(f[x]); w[x] += w[ret]; return f[x]; } } -
合并
正常情况下，我们合并为 \(\tt f[root(x)]=root(y)\)，但是这里有权值，我们需要计算出 \(root(x) \to root(y)\) 的权值，把 \(root(x)\) 所在的集合看作一层，可以发现 \(root(x) \to root(y)=x \to root(y)\)，答案也就是 \(\tt w[root(x)] = w[y] + v - w[x]\)。
void merge(int x, int y, int v) { int xx = find(x), yy = find(y); if (xx != yy) { f[xx] = yy; w[xx] = w[y] + v - w[x]; } }
例题：
有一个 \([0,n]\) 的区间，其中每个元素均为正整数，给定 \(m\) 条信息，每条信息给定 \(l,r,w\)，表示 \([l,r]\) 区间的和为 \(w\)，请你找出有多少条假信息。
设 \(s_i\) 表示前缀和，则 \([l,r]\) 的和为 \(w\) 可以转化为 \(s_r-s_{l-1}=w\)，因此合并 \((l-1 \leftrightarrow r, w)\)，如果发现已经合并了，则 \(w[l-1]-w[r] \neq w\) 时为假消息。
提交记录：https://vjudge.net/solution/47921858
存在两个集合，有 \(m\) 条信息，每次给出 \(x,y\)，表示 \(x,y\) 在不同的集合。如果所有信息没有冲突，输出
No suspicious bugs found!，否则输出Suspicious bugs found!。
这道题做法有两种：种类并查集或边权并查集。
这里先说边权并查集，这里我们将 \(w[x] \bmod 2\)，用 \(0\) 和 \(1\) 表示两个集合，如果已经合并，且 \(w[x] \bmod 2 \neq w[y] \bmod 2\)，那么就会与前面信息冲突。
提交记录：https://vjudge.net/solution/47923266
初始时有 \(30000\) 个数列，有两种操作，\(\tt M \ i \ j\) 表示将 \(i\) 所在的数列接到 \(j\) 所在的数列后面，\(\tt C \ i \ j\) 表示询问 \(i \sim j\) 之间元素的个数，不包括 \(i\) 和 \(j\)，如果它们不在同一个数列，输出 \(-1\)。
这道题的特殊之处在于合并是将数列接到后面，并不是直接合在一起，路径压缩时并不影响，我们回溯时已经做过处理。下面核心就是合并了。假设将数列 \(x\) 接到 \(y\) 后面，那么我们只需要更新 \(x\) 这个集合，可以发现，\(x\) 的根节点到 \(y\) 的根节点的距离就是 \(\tt size[y]\)，如下：
现在就很简单了，答案就是 \(\tt | w[i]-w[j] | - 1\)。
提交记录：https://www.luogu.com.cn/record/140752349
有三种动物 \(A,B,C\)，捕食关系是 \(A \to B\)，\(B \to C\)，\(C \to A\)（\(A \to B\) 表示 \(A\) 吃 \(B\)），有 \(n\) 个动物是 \(A,B,C\) 其中之一，有 \(m\) 句话，有如下两种：
1 x y表示 \(x\) 和 \(y\) 是同类。2 x y表示 \(x \to y\)。你要判断有多少假话，假话有如下特点：
- \(x\) 或 \(y\) 大于 \(n\)。
- 表示 \(x \to x\)。
- 与前面的真话冲突。
难度很大的一道题。同样也是两种做法，种类并查集做法在后面。
我们需要三种权值，用 \(0\) 表示同类，\(1\) 表示吃父亲节点，\(2\) 表示被父亲节点吃。路径压缩时我们将 \(w[x] \bmod 3\) 来保证 \(w[x] \in \{0,1,2\}\)。接下来是合并，当 \(op=1\) 时，如果他们存在吃与被吃的关系，就是假的，即 \((w[x]-w[y]+3) \bmod 3 \neq 0\)。当 \(op=2\) 时，如果他们存在同类或 \(y\) 吃 \(x\) 的情况，就是假的，即 \((w[x]-w[y]+3) \bmod 3 \neq 1\)。合并时 \(w[root(x)]=(w[y]+v-w[x]+3) \bmod 3, \ v \in \{0,1,2\}\)。
提交记录：https://www.luogu.com.cn/record/140841174
种类并查集：
一个并查集不够用怎么办，那就开多个。
有两个集合，以及 \(n\) 个元素。给定 \(m\) 条信息，每条信息为 \(x \ y \ w\)，表示将 \(x,y\) 放在同一集合的花费是 \(w\)。你要把这 \(n\) 个元素放入两个集合，尽可能让需要的花费的最大值最小。
我们可以先将消息按照 \(w\) 从大到小排序，如果有一条信息无法将 \(x\) 和 \(y\) 放到不同的集合中，那么这条信息的 \(w\) 就是答案。问题转化为给定 \(x,y\)，判断 \(x,y\) 是否能在不同的监狱。我们可以建立 \(2n\) 个节点的并查集，将 \(x\) 和 \(y+n\) 合并，\(x+n\) 和 \(y\) 合并，表示在不同的集合。我们用样例来演示：
前三个都能够放在不同的监狱，但是 \(2 \ 3\) 不能放到同一个监狱，因为 \(1\) 和 \(2\) 不能放同一集合，\(1\) 和 \(3\) 不能放同一集合，那么必然 \(2\) 和 \(3\) 得放到同一集合。这里只有相对关系，那么单独集合内不会有连线，因此 \(u\) 和 \(v\) 或者 \(u+n\) 和 \(v+n\) 已经合并，就做不到 \(u,v\) 在不同的集合且花费为 \(0\)。
提交记录：https://www.luogu.com.cn/record/117647741
这里我们讲解种类并查集的做法，建立 \(2n\) 个节点的并查集，与关押罪犯是一样的。
这里讲解种类并查集的做法。为了方便理解，下面均使用图片讲解。对于同类，我们直接在它们自己的类群中合并就可以了。
第一句肯定是错误的，第二句是 \(1\) 吃 \(2\)，根据题目中的 \(A\) 吃 \(B\)，\(B\) 吃 \(C\)，\(C\) 吃 \(A\)，我们应该将 \(A\) 中的 \(1\) 和 \(B\) 中的 \(2\) 合并，\(B\) 中的 \(1\) 和 \(C\) 中的 \(2\) 合并，\(C\) 中的 \(1\) 和 \(A\) 中的 \(2\) 合并，实际上，另外两个集合对于一个集合来说，一个是捕食，一个是天敌。接下来第二句话也是正确的。到第三句时是合并，我们该如何判断这句消息是不是真的呢？
既然要保证是同类，根据题目中的 \(A\) 吃 \(B\)，\(B\) 吃 \(C\)，\(C\) 吃 \(A\)，应该有 \(x,y\) 不能在不同的类群，即 \(x\) 不能吃 \(y\)，\(y\) 不能吃 \(x\)，也就是说，\(x,y+n\) 和 \(x+n,y\) 是没有合并的。这里没有合并，这句话也是可以的。然后是第四句话。
这句话表示 \(3\) 吃 \(1\)，首先他们必定不在同一类群，即 \(x,y\) 是没有合并的。然后就是 \(1\) 不能吃 \(3\)，也就是 \(x,y+n\) 是没有合并的（时刻记住\(A\) 吃 \(B\)，\(B\) 吃 \(C\)，\(C\) 吃 \(A\)），这句话中，\(1\) 和 \(3\) 在同一类群中，是错误的。接下来是最后一句话。
提交记录：https://www.luogu.com.cn/record/140736969
标签：int,查集,合并,集合,root,find From： https://www.cnblogs.com/unino/p/17965175/bing-cha-ji