欢迎大家访问我的算法提高课补全计划!算法提高课补全计划。欢迎点赞收藏!
扩展域并查集好题。
首先将三种动物分别划分成三个域:$A, B$ 和 $C$。
将动物 $x$ 在 $k$ 域里的节点记做 $k(x)$。
如果两个动物 $x, y$ 是同种动物,那么连边 $A(x) \rightarrow A(y)$,$B(x) \rightarrow B(y)$,$C(x) \rightarrow C(y)$,代表知道了 $x, y$ 中的任意一种动物种类,都可以知道另一种的种类与他相同。
如果 $x$ 吃 $y$,那么连边 $A(x) \rightarrow B(y)$,$B(x) \rightarrow C(y)$,$C(x) \rightarrow A(y)$。
判断矛盾冲突:
-
如果 $x, y > n$,直接不合法。
-
如果 $x, y$ 同类,但是存在 $x$ 吃 $y$ 或 $y$ 吃 $x$ 的情况(即 $A(x) \rightarrow B(y)$,$B(x) \rightarrow C(y)$,$C(x) \rightarrow A(y)$,$A(y) \rightarrow B(x)$,$B(y) \rightarrow C(x)$,$C(y) \rightarrow A(x)$ 中出现任意一种),则不合法。
-
如果 $x, y$ 不是同类,则如果 $x, y$ 在同类之间有连边,或者存在 $y$ 吃 $x$ 则不合法。
时间复杂度 $O(n \log n)$。
#include <iostream>
#include <cstdio>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
using namespace std;
const int N = 150010;
int fa[N], n, m, s;
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int main() {
scanf("%d%d", &n, &m);
rep(i, 1, n * 3) fa[i] = i;
while (m -- ) {
int op, x, y;
scanf("%d%d%d", &op, &x, &y);
int xa = find(x), ya = find(y);
if (x > n or y > n) { s ++ ; continue; }
int xb = find(x + n), yb = find(y + n);
int xc = find(x + n + n), yc = find(y + n + n);
if (op & 1) {
if (xa == yb or xb == yc or xc == ya) { s ++ ; continue; }
if (ya == xb or yb == xc or yc == xa) { s ++ ; continue; }
fa[xa] = ya, fa[xb] = yb, fa[xc] = yc;
} else {
if (xa == ya or xb == yb or xc == yc) { s ++ ; continue; }
if (ya == xb or yb == xc or yc == xa) { s ++ ; continue; }
fa[xa] = yb, fa[xb] = yc, fa[xc] = ya;
}
} cout << s << endl; return 0;
}
$orz$