ACM-1019

Problem S

Time Limit : 15000/5000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 3   Accepted Submission(s) : 2

Problem Description <b>Background </b><br>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. <br><br><b>Problem </b><br>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.<br>  

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!

<div style='font-family:Times New Roman;font-size:14px;background-color:F4FBFF;border:#B7CBFF 1px dashed;padding:6px'><div style='font-family:Arial;font-weight:bold;color:#7CA9ED;border-bottom:#B7CBFF 1px dashed'><i>Hint</i></div>Huge input,scanf is recommended.</div>
        

做了這題才再次發現自己對并查集的了解真的隻是一些皮毛，并查集的很多進階應用我都還不懂，而這題隻是種類并查集中最簡單的 .

假設有

1，2

2，3

即1--2--3， 明顯相鄰的兩個不能是同性别的，如果相鄰兩個是同性的，那麼說明就可能是有同志存在。

上面假設1是男性，用false來代替，那麼按順序分别是false, true, false

假設  再加個關系3， 1

那麼由于1和3已經都有值了，都是false，說明可能有同志。

種類并查集的關鍵在于與結點與根結點的距離， 如果距離是奇數那麼性别就和跟結點相反，如果是偶數就和跟結點性别相同。

代碼：

#include<cstdio>  

#define N 2005  

using namespace std;  

int f[N],rank[N], n, k;  

bool flag;  

inline void init(){  

    flag=false;  

    for(int i=0; i<=n; ++i)  

        f[i]=i, rank[i]=0;  

}  

int find(int x){  

    if(x==f[x])return f[x];  

    int t=find(f[x]);  

    rank[x] = (rank[f[x]]+rank[x])&1;  

    f[x]=t;  

    return f[x];  

}  

void Union(int x, int y){  

    int a=find(x), b=find(y);  

    if(a==b){  

        if(rank[x]==rank[y])  

            flag=true;  

        return;  

    }  

    f[a]=b;  

    rank[a] = (rank[x]+rank[y]+1)&1;  

}  

int main(){  

    int T,a,b,cas=1;  

    scanf("%d",&T);  

    while(T--){  

        scanf("%d%d",&n,&k);  

        init();  

        for(int i=0; i<k; ++i){  

            scanf("%d%d",&a,&b);  

            if(flag)continue;  

            Union(a,b);  

        }  

        printf("Scenario #%d:\n",cas++);  

        if(flag)printf("Suspicious bugs found!\n");  

        else printf("No suspicious bugs found!\n");  

        printf("\n");  

    }  

    return 0;  

}