种类并查集的复习。
再次复习了rank数组代表的是指向父节点。rank[a]= a->fa.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
|
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> using namespace std; const int N = 10005; int pre[N], ran[N]; int a, b; void () { for (int i = 1; i <= a;i++) { pre[i] = i; ran[i] = 0; } } int find(int x) { if(x==pre[x]) { return pre[x]; } else { int f = find(pre[x]); ran[x] = (ran[pre[x]] + ran[x]) % 2; pre[x]=f; return f; } } int flag; void un(int x,int y) { int fx=find(x); int fy=find(y); if(fx==fy) if(ran[x]%2==ran[y]%2) { flag = 1; return; } ran[fx] = (-ran[x] + ran[y] + 1) % 2; pre[fx] = fy; return; } int main() { int t; cin >> t; int cas = 1; while(t--) { flag = 0; cin >> a >> b; init(); for (int i = 1; i <= b;i++) { int m, n; cin >> m >> n; if(flag) continue; un(m,n); } printf("Scenario #%d:n",cas++); if(flag)printf("Suspicious bugs found!n"); else printf("No suspicious bugs found!n"); printf("n"); } }
|
近期评论