hdu1829 题解

链接:hdu1829

Scenario #2:
No suspicious bugs found!

题解

  • 这题很好玩,找gay 也是带权并查集
  • 算一下向量偏移量就好了 压缩路径的偏移量算错了wa了一发,输出标记错了又wa一发。。。
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

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=1e4+7;
int f[N],rl[N],T,a,b,cnt,ans,n,m;

int (int x){
if(f[x]==x)return x;
int t=find(f[x]);
rl[x]=(rl[x]+rl[f[x]])&1;
return f[x]=t;
}

inline int un(int x,int y){
int a=find(x);
int b=find(y);
if(a==b)if(rl[x]==rl[y])return ans=1;
f[b]=a;
rl[b]=(rl[x]-rl[y]+1)&1;
return 0;
}


int main(){
scanf("%d",&T);
while(T--){
ans=0;
scanf("%d%d",&n,&m);
memset(rl,0,sizeof(rl));
rep(i,1,n)f[i]=i;
printf("Scenario #%d:n",++cnt);
rep(i,1,m){
scanf("%d%d",&a,&b);
if(ans)continue;
if(un(a,b))puts("Suspicious bugs found!n");
}
if(!ans)puts("No suspicious bugs found!n");
}
return 0;
}