hdu1829

发表于 | 分类于 ， ， | 阅读数 次

链接:hdu1829

Description

  • Background
  • Professor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature
  • two different genders and that they only interact with bugs of the opposite gender. In his experiment,

  • individual bugs and their interactions were easy to identify, because numbers were printed on their backs.

  • Problem

  • Given a list of bug interactions, decide whether the experiment supports his assumption of two genders with
  • no homosexual bugs or if it contains some bug interactions that falsify it.

    Input

  • The first line of the input contains the number of scenarios. Each scenario starts with one line giving the
  • number of bugs (at least one, and up to 2000) and the number of interactions (up to 1000000) separated by a
  • single space. In the following lines, each interaction is given in the form of two distinct bug numbers
  • separated by a single space. Bugs are numbered consecutively starting from one.

    Output

  • The output for every scenario is a line containing “Scenario #i:”, where i is the number of the scenario
  • starting at 1, followed by one line saying either “No suspicious bugs found!” if the experiment is consistent
  • with his assumption about the bugs’ sexual behavior, or “Suspicious bugs found!” if Professor Hopper’s
  • assumption is definitely wrong.

    Sample Input

    2
    3 3
    1 2
    2 3
    1 3
    4 2
    1 2
    3 4

    Sample Output

    Scenario #1:
    Suspicious bugs found!
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<iostream>
#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 find(int x){
    if(f[x]==x)return x;
    int t=find(f[x]);
    rl[x]=(rl[x]+rl[f[x]])&1;   //rl[x] 表示x与f[x]的关系 
    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;
}