首页 > 代码库 > POJ2492A Bug's Life【并查集+根节点偏移】
POJ2492A Bug's Life【并查集+根节点偏移】
大意：
告诉你一些关系
a b 代表 a 和 b 是异性
问这些关系中有没有错误的语句
分析：
有并查集维护其是否在同一个集合之中 在开一个num数组来维护对于根节点的偏移量
在find的时候只需要递归到根节点返回的过程中把num数组进行维护就可以了
在进行合并的时候我们需要考虑到把一个点的根节点并到另一个的根节点上
所以要根据u和v的偏移关系推广到u和v的根节点的关系之上
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = 2005; 7 int fa[maxn], num[maxn]; 8 9 void init(int n) {10 for(int i = 0; i <= n; i++) {11 fa[i] = i;12 num[i] = 0;13 }14 }15 16 int find(int i) {17 if(i == fa[i]) {18 return i;19 }20 int fi = fa[i];21 fa[i] = find(fa[i]);22 num[i] = (num[fi] + num[i]) % 2;23 return fa[i];24 }25 26 void unin(int u, int v) {27 int fu = find(u); int fv = find(v);28 if(fu != fv) {29 fa[fv] = fu;30 if(num[fu] == num[u]) {31 if(num[fv] == num[v]) {32 num[fv] = num[fu] == 0 ? 1 : 0;33 } else {34 num[fv] = num[fu] == 0 ? 0 : 1;35 }36 } else {37 if(num[fv] == num[v]) {38 num[fv] = num[fu] == 0 ? 0 : 1;39 } else {40 num[fv] = num[fu] == 0 ? 1 : 0;41 }42 }43 }44 }45 46 int main() {47 int t;48 int n, m;49 int a, b;50 scanf("%d",&t);51 for(int kase = 1; kase <= t; kase++) {52 scanf("%d %d",&n, &m);53 init(n);54 bool flag = false;55 while(m--) {56 scanf("%d %d", &a, &b);57 if(find(a) != find(b) ) {58 unin(a, b);59 } else {60 if(num[a] == num[b]) {61 flag = true;62 }63 }64 }65 printf("Scenario #%d:\n", kase);66 if(flag) {67 puts("Suspicious bugs found!");68 } else {69 puts("No suspicious bugs found!");70 }71 puts("");72 }73 return 0;74 }
POJ2492A Bug's Life【并查集+根节点偏移】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。