并查集带偏移向量 HDU1829

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #include <queue>
 6 
 7 using namespace std;
 8 
 9 int father[2010];
10 int offset[2010];
11 int flag;
12 
13 void init(int n)
14 {
15     for(int i=1;i<=n;i++)
16     {
17         father[i]=i;
18         offset[i]=0;
19     }
20     flag=1;
21 }
22 
23 int root(int x)
24 {
25     if(x!=father[x])
26     {
27         int tmp=father[x];
28         father[x]=root(father[x]);
29         offset[x]=(offset[x]+offset[tmp])%2;
30     }
31     return father[x];
32 }
33 
34 void merge(int x,int y)
35 {
36     int fx=root(x);
37     int fy=root(y);
38     if(fx!=fy)
39     {
40         father[fx]=fy;
41         offset[fx]=(offset[y]+1-offset[x])%2;
42     }
43     root(x);
44 }
45 
46 int main()
47 {
48     int T;
49     cin>>T;
50     for(int s=1;s<=T;s++)
51     {
52         int n,m;
53         scanf("%d%d",&n,&m);
54         init(n);
55         int x,y;
56         for(int i=0;i<m;i++)
57         {
58             scanf("%d%d",&x,&y);
59             if(flag)
60             {
61                 merge(x,y);
62                 if(offset[x]==offset[y])
63                     flag=0;
64             }
65         }
66         cout<<"Scenario #"<<s<<":"<<endl;
67         if(flag)
68             cout<<"No suspicious bugs found!"<<endl;
69         else
70             cout<<"Suspicious bugs found!"<<endl;
71         cout<<endl;
72     }
73     return 0;
74 }
View Code