和食物链类似，需要计算集合之间的关系。这里明确一点即可，就是根节点的初始值是都相同，为0。
只要在路径压缩和合并的时候注意即可。
#include#include #include using namespace std; #define LLEN 2005 int c, g; int p[LLEN], f[LLEN]; void init() { for(int i = 0; i <= c+5; i++) { p[i] = i; f[i] = 0; } } int find(int x) { if(p[x] != x) { int k = p[x]; p[x] = find(p[x]); f[x] = (f[x] + f[k])%2; } return p[x]; } int unionSet(int x, int y) { int r1 = find(x); int r2 = find(y); if(r1 == r2) { if(f[x] == f[y]) return 1; return 0; } p[r2] = r1; f[r2] = (f[x] - f[y] + 1)%2; return 0; } int main() { int t; scanf("%d", &t); for(int cse = 1; cse <= t; cse++) { int flag = 0; scanf("%d%d", &c, &g); init(); for(int i = 0; i < g; i++) { int a, b; scanf("%d%d", &a, &b); if(!flag && unionSet(a, b)) flag = 1; } printf("Scenario #%d:\n", cse); if(1 == flag) { printf("Suspicious bugs found!\n\n"); } else { printf("No suspicious bugs found!\n\n"); } } return 0; }