并查集
并查集是一种高效的数据结构,能够在接近O(1)的合并两个集合\查询两个元素是否在一个集合中.并查集在使用过程中还可以维护许多额外信息.
并查集用数组存储,存储为树的形式,一开始所有元素都自己单独形成一个并查集,当两个集合需要合并时就将之间某个集合的祖先结点指向另一个集合即可.
p[x]是x结点的祖先编号,祖先结点x的特征是p[x] = x;
初始化:
int p[N]; //节点
for (int i = 1; i <= n; i++) {
p[i] = i;//节点赋予编号
//!开始时每个集合都是一个独立的集合,并且都是等于自己本身下标的数,一开始都是祖先结点
}
在查询某两个集合是否在一个集合中是,使用如下定义的find函数:
inline int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
//上面 x:p[x]也可以是p[x]:p[x]
p[x]=find(p[x])会不断的套p[p[p[p[p[p[p[x....]]]]]]]相当于持续不断的访问父节点来寻找祖先,直到找到p[x]=x;
直到套很多层后p[p[p[p[p[…x]]]]] = x的时候回溯,回溯的时候由于有p[x] = find(p[x])这句,所以每一层的节点都会直接指向x,相当于把子节点到祖先结点的路径长度变为1, 下次再从这些子节点访问祖先结点只要O(1),这就是路径压缩.
合并集合:
p[find(a)] = find(b);//a的祖先的祖先(就是a祖先自己)是b的祖先. 合并了两个集合
判断两个元素是否在一个集合
if (find(a) == find(b)) {//a的祖先等于b的祖先
puts("Yes");
} else {
puts("No");
}
另:对于并查集集合性质的维护等价于在维护祖先结点的性质,例如集合中元素的数量,要以祖先结点为idx
例题
https://www.acwing.com/problem/content/242/
动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。
现有 N 个动物，以 1?N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这 N 个动物所构成的食物链关系进行描述：
第一种说法是 1 X Y，表示 X 和 Y 是同类。
第二种说法是 2 X Y，表示 X 吃 Y。
此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K句话有的是真的，有的是假的。
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
当前的话与前面的某些真的话冲突，就是假话；
当前的话中 X 或 Y 比 N 大，就是假话；
当前的话表示 X 吃 X，就是假话。
你的任务是根据给定的 N 和 K 句话，输出假话的总数。
输入格式
第一行是两个整数 N 和 K，以一个空格分隔。
以下 K 行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中 D
表示说法的种类。 若 D=1，则表示 X 和 Y 是同类。 若 D=2，则表示 X 吃 Y。 输出格式
只有一个整数，表示假话的数目。
数据范围
1≤N≤50000,
0≤K≤100000
输入样例：
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
输出样例：
3
本题可以维护一些集合,对于某种特定的动物x它对应了三个集合,设为x,x+n,x+n+n,表示的含义为x是同类域,x+n是捕食域,x+n+n是天敌域然后判断同类只要查询是否在一个集合,如果有a吃b的关系就把b与a+n合并,把b+n(b的捕食域)与a的天敌域(a+n+n)合并,把b+n+n(b的天敌域)与a的同类域(a)合并即可.
#include <iostream>
using namespace std;
const int N = 1e5 * 3;
int pt[N];
// x是同类域.
// x+n是捕食域
// x+n+n是天敌域
int ans;
int fa(int x) { return pt[x] == x ? pt[x] : pt[x] = fa(pt[x]); }
void merge(int x, int y) { pt[fa(x)] = fa(y); }
int main() {
int n, k;
cin >> n >> k;
int a, b, p;
for (int i = 1; i <= 3 * n; ++i) {//从1开始 从0开始也可以
pt[i] = i;
}
for (int i = 0; i < k; ++i) {
scanf("%d%d%d", &p, &a, &b);
if (a > n || b > n) {
ans++;
} else if (p == 1) {//若是同类
//!注意不能用反过来的条件判断 比如f(a)!=f(b) 不然有些真话无法插入进去
if (fa(a) == fa(b+n)||fa(a) == fa(b+n+n)) {//如果b吃a或a吃b 注意符号是||
ans++;
} else {
merge(a, b);
merge(a + n, b + n);
merge(a + n + n, b + n + n);
}
} else {//若a吃b
if (a==b||fa(a) == fa(b+n)||fa(a)==fa(b)) {//如果a,b是一个东西 或 a和b为同类 或 b吃a
ans++;
} else {
merge(a + n, b);
merge(a + n + n, b + n);
merge(a, b + n + n);
}
}
}
cout << ans << endl;
return 0;
}
