题目1：洛谷 P2024
题意
-
有 \(n\) 个动物，每个动物都是 \(A,B,C\) 中的一种，其中 \(A\) 吃 \(B\)，\(B\) 吃 \(C\)，\(C\) 吃 \(A\)。给定两种食物链关系。
- 第一种说法是
1 X Y，表示 \(X\) 和 \(Y\) 是同类。 - 第二种说法是
2 X Y，表示 \(X\) 吃 \(Y\)。
- 第一种说法是
-
这两种关系有 \(k\) 条，一条关系是真话满足当前的话与前面所有的真话冲突不冲突，且 \(X，Y \le n\) 且 \(X \ne Y\)。请输出假话的数量。
-
\(1 \le n \le 5 \times 10^4,1 \le k \le 10^5\)。
思路
-
这道题显然是并查集。令 \(i\) 对应的集合为与动物 \(i\) 同类的动物， \(i + n\) 对应的集合为 \(i\) 吃的动物， \(i + n + n\) 对应的集合为吃 \(i\) 的动物。
-
如果当前关系为第一种，这条关系为真必须满足（为假答案数 \(+1\)，以下只考虑了第一种情况，后两种自己判一下）：
- \(X\) 对应的集合不是 \(Y + n\) 对应的集合。
- \(Y\) 对应的集合不是 \(X + n\) 对应的集合。
-
否则如果是真话需满足：
- \(X\) 对应的集合不是 \(Y + n\) 对应的集合。
- \(Y\) 对应的集合不是 \(Y\) 对应的集合。
-
如果当前关系为第一种且为真，将以下集合合并（为假答案数 \(+1\)，以下只考虑了第一种情况，后两种自己判一下）：
- \(X\) 对应的集合不是 \(Y\) 对应的集合。
- \(X + n\) 对应的集合不是 \(Y + n\) 对应的集合。
- \(X + n\) 对应的集合不是 \(Y + n + n\) 对应的集合。
-
如果当前关系为第二种种且为真，将以下集合合并：
- \(X + n\) 对应的集合不是 \(Y\) 对应的集合。
- \(X\) 对应的集合不是 \(Y + n + n\) 对应的集合。
- \(X + n + n\) 对应的集合不是 \(Y + n\) 对应的集合。
-
最后输出答案数即可。
-
时间复杂度
- 并查集维护合并操作：\(O(n \times log \ n)\)。
- \(k\) 次询问：\(O(k)\)。
- 总时间复杂度：\(O(n \times log \ n +k)\)
const int MAXN = 5e4 + 5;
int n, q, c, op, x, y, fa[MAXN * 3];
int Find(int x){
return (fa[x] ? fa[x] = Find(fa[x]) : x);
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> q;
for(int i = 1; i <= q; i++){
cin >> op >> x >> y;
if(x > n || y > n || (x == y && op == 2)){ //特判后两种情况
c++;
continue;
}
int xa = Find(x), ya = Find(y); // x, y 对应的集合的代表
int xb = Find(x + n), yb = Find(y + n); // x + n, y + n 对应的集合的代表
int xc = Find(x + n + n), yc = Find(y + n + n); // x + n + n, y = n + n 对应的集合的代表
if(op == 1){
if(xa == yb || xb == ya){ //假话
c++;
}else{ //真话
fa[xa] = (xa == ya ? 0 : ya);
fa[xb] = (xb == yb ? 0 : yb);
fa[xc] = (xc == yc ? 0 : yc);
}
}else{
if(xa == ya || yb == xa){ //假话
c++;
}else{ //真话
fa[ya] = (ya == xb ? 0 : xb);
fa[yb] = (xc == yb ? 0 : xc);
fa[xa] = (xa == yc ? 0 : yc);
}
}
}
cout << c;
return 0;
}
题目2：CSES 2101
题意
-
有 \(n\) 个点，\(m\) 条无向边边和 \(q\) 组询问。每组询问给定两个点 \(x,y\)，问 \(x,y\) 在加入第几条边后两个点从不连通到连通，如果加入 \(m\) 条边后仍不连通，输出 \(-1\)。
-
\(1 \le n, m, q \le 2 \times 10^5\)。
思路
-
题意简化为：第 \(i\) 的边权为 \(i\)，每组询问查询并查集建出森林后 \(x\) 到 \(x,y\) 的最近公共祖先 \(z\) 的路径上的边权最大值和 \(y\) 到 \(z\) 的路径上的边权最大值的最大值。
-
找最近公共祖先可以下操作（找最近公共祖先时可以顺便求一下答案）：
- 若 \(x\) 的子树大小 \(\le\) \(y\) 的子树大小，\(x\) 变为 \(x\) 的父亲。否则 \(y\) 变为 \(y\) 的父亲。直到 \(x = y\)。
- 如果 \(x\) 和 \(y\) 都是某个树的根但是还有往上走，就说明原先的 \(x,y\) 不在同一个树内。
-
时间复杂度
- 输入 \(m\) 条道路：\(O(m)\)。
- 并查集维护合并集合：\(O(n \times log \ n)\)。
- \(q\) 组询问，每组询问 \(x,y\) 最多往上跳 \(log \ n\) 次，时间复杂度：\(O(q \times log \ n)\)。
- 总时间复杂度：\(O(m + (n + q) \times log \ n)\)。