首页 > 代码库 > POJ 2492 (简单并查集) A Bug's Life

POJ 2492 (简单并查集) A Bug's Life

2024-07-20 15:55:42   225人阅读

题意：有编号为1~n的虫子，开始假设这种昆虫是异性恋。然后已知xi 和 yi进行交配，根据已知情况分析能否推理出其中是否有同性恋

这道题和 POJ 1182 食物链 十分相似，不过在更新与父节点关系的时候要简单一些

sex数组保存的是与父节点的性别关系，如果与父节点是同性，则为0，否则是1

每次路径压缩的同时要更新sex[a] = (sex[a] + sex[temp]) % 2;

还有就是如果x 和 y 不在一个集合，两棵树进行合并的时候，考虑x px y py 四者之间的关系，有

parent[px] = py;sex[px] = 1 - (sex[x] ^ sex[y]);

这个在纸上模拟一下就很容易得出来

 

在敲代码的过程中还是犯了两个低级的小错误，因为一旦我们发现了存在同性恋，便可以输出结果了，不过要对剩余未读入的数据“忽略”

因为i可能是break出来的，这次循环没有完成，i也没有自增，所以在“忽略”的循环里面，i首先要自增一下

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 const int maxn = 2000 + 10; 8 int parent[maxn], sex[maxn]; 9 10 int GetParent(int a)11 {12     if(parent[a] == a)    return a;13     int temp = parent[a];14     parent[a] = GetParent(parent[a]);15     sex[a] = (sex[a] + sex[temp]) % 2;16     return parent[a];17 }18 19 int main(void)20 {21     #ifdef LOCAL22         freopen("2492in.txt", "r", stdin);23     #endif24 25     int T, kase;26     scanf("%d", &T);27     for(kase = 1; kase <= T; ++kase)28     {29         int n, m, i;30         int x, y;31         bool flag = false;32         scanf("%d%d", &n, &m);33         for(int i = 0; i <= n; ++i)34         {35             parent[i] = i;36             sex[i] = 0;37         }38         for(i = 0; i < m; ++i)39         {40             scanf("%d%d", &x, &y);41             int px = GetParent(x);42             int py = GetParent(y);43             if(px == py)44             {45                 if(sex[x] == sex[y])46                 {47                     flag = true;48                     break;49                 }50             }51             else52             {53                 parent[px] = py;54                 sex[px] = 1 - (sex[x] ^ sex[y]);55             }56         }57         for(++i; i < m; ++i)58             scanf("%d%d", &x, &y);59         printf("Scenario #%d:\n%suspicious bugs found!\n\n", kase, flag ? "S" : "No s");60         //if(kase < T)    printf("\n");61     }62     return 0;63 }
代码君

 

POJ 2492 (简单并查集) A Bug's Life


联系
我们