题解 SP3377 【BUGLIFE - A Bug's Life】

本文同步发布于[Handwer's Blog](https://blog.handwer-std.top/) # 题目描述 见题面。 # 解题思路 显然这是一个并查集，但并不是一个裸的并查集 我们要多维护一个数组`rel[]`，其中`rel[i]`表示`i`和它的祖先的关系（relative）。我们定义`rel[i]`表示两种性别，当根节点相同且`rel[]`相同时，它们就是同性恋 `rel[]`的更新方式： ``` (in Find(x)) rel[x] = (rel[x] + rel[U[x]]) % 2; ``` ``` (in Union(x, y)) int fx = Find(x), fy = Find(y); ... rel[fx] = (rel[x] + rel[y] + 1) % 2; ``` `rel[]`的判断方式： ``` (in Union(x, y)) if (fx == fy) { if (rel[x] == rel[y]) suspiciousFound = true; return; } ``` 剩下的照常写就行 注意路径压缩要分开写，先创建一个变量存它的祖先节点再更新 ~~按秩合并没写过不知道~~ # 代码实现 ~~你们最喜欢的~~代码实现： ``` #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int MAXM = 1000000 + 10; int n, m; int U[MAXM], rel[MAXM]; bool flag; int Find(int x) { if (x != U[x]) { // 把路径压缩撑开写 int fux = Find(U[x]); rel[x] = (rel[x] + rel[U[x]]) % 2; // 更新rel数组 // 1 1 -> 0 // 1 0 / 0 1 -> 1 // 0 0 -> 0 // 其实是一个异或的过程 U[x] = fux； // qwq } return U[x]; } void Union(int x, int y) { int fx = Find(x), fy = Find(y); if (fx == fy) { if (rel[x] == rel[y]) flag = true; // 判断是否同性 return; } U[fx] = fy; rel[fx] = (rel[x] + rel[y] + 1) % 2; // 更新rel数组 } int main(int argc, char *const argv[]) { int t; scanf("%d", &t); int _t = 0; while (t --> 0) { memset(U, 0, sizeof(U)); memset(rel, 0, sizeof(rel)); n = 0, m = 0, flag = false; scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) U[i] = i; for (int i = 1; i <= m; ++i) { int x, y; scanf("%d %d", &x, &y); Union(x, y); } printf("Scenario #%d:\n", ++_t); if (flag) printf("Suspicious bugs found!\n"); else printf("No suspicious bugs found!\n"); } return 3; // qwq } ```