加权并查集mod2模板 本体的难点是bug的释义(笑)
#include <iostream> #include <string> #include <cstdio> #include <cmath> #include <cstring> #include <queue> #include <map> #include <set> #include <algorithm> using namespace std; int father[5005],sum[5005]; int find(int x) { if(father[x] != x) { int tmp = father[x]; father[x] = find(tmp); sum[x] = (sum[x] + sum[tmp]) % 2; } return father[x]; } void merge(int x,int y) { int tx = find(x); int ty = find(y); //printf("x = %d y = %d tx = %d ty = %d ", x, y, tx, ty); if(tx == ty) return; father[tx] = ty; //printf("father(1) = %d ",father[1]); sum[tx] = (sum[x] - sum[y] + 1) % 2; return; } int main() { int t; scanf("%d",&t); for(int kase = 1; kase <= t; kase++) { int n, m; bool flag = true; scanf("%d%d", &n, &m); //Initiate for(int i = 0; i <= n; i++) { father[i] = i; sum[i] = 0; } while(m--) { int a, b; scanf("%d%d", &a, &b); if(find(a) == find(b)) { if(sum[a] != (sum[b] + 1) % 2){ //printf("a = %d b = %d ", a, b); flag = false; } } else merge(a, b); } printf("Scenario #%d: ", kase); if(flag) printf("No suspicious bugs found! "); else printf("Suspicious bugs found! "); } return 0; }