poj2492A Bug's Life(并查集详解)

Time Limit: 10000MS Memory Limit: 65536K

Total Submissions: 25418 Accepted: 8278

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!

Hint

Huge input,scanf is recommended.

Source

TUD Programming Contest 2005, Darmstadt, Germany

[Submit]   [Go Back]   [Status]   [Discuss]

 

说起这道题令我很惭愧，初学并查集，但是这道题我想了两天时间，一直都不明白网上的高手们的题解。

可能是自己的水平真的很水。

我几乎想放弃这道题，或者给自己一个借口以后回来再研究但是想了一想大牛都是要坚持不懈的，而自己又在为这个目标而奋斗。

所以就咬着牙坚持着想。后来就~~有了这篇解题报告。。

 

#include<cstdio>  
#include<cstring>  
//using namespace std;  
int f[2023],rank[2023];//rank[]表示0为和根节点是同性，1为和根节点是异性  
void Init(int n)  
{  
    for(int i=0;i<=n+1;i++)  
    {  
        f[i] = i;  
        rank[i] = 0;  
    }  
}  
int work(int x)  
{  
    if(x==f[x])  
        return x;  
    int tem = f[x];  
    int ss = rank[tem];  
    f[x] = work(f[x]);  
    rank[x] = rank[x]^rank[tem];  //rank[tem]是代表x的父亲节点和最新的根节点的关系  
                                    //现在知道了rank[tem]和自己跟父亲的关系即右边的rank[x]，  
    return f[x];                //要更新自己跟最新根节点的关系，可知这是异或的关系。  
                        //例如父亲节点跟最新节点是1即是异性，而自己跟父亲节点是0即是同性，  
                        //那自己跟最新节点就是1即是异性。。  
                        //还有三种情况可以自己列出来。。     
}                                     
int main()  
{  
    int n;  
    scanf("%d",&n);  
    int bugnum,ed,x,y;  
    for(int i=1;i<=n;i++)  
    {  
        scanf("%d%d",&bugnum,&ed);  
        Init(bugnum);  
        int re = 0;  
        for(int j=0;j<ed;j++)  
        {  
            scanf("%d%d",&x,&y);  
            if(!re)  
            {  
                int xx = work(x);  
                int yy = work(y);  
                if(xx==yy && rank[x]==rank[y])  
                    re = 1;  
                else  
                {  
                    f[xx] = yy;  
                    rank[xx] = !(rank[x]^rank[y]); //这句话是将两棵树的根节点合起来，那本来两棵树的  
                }                       //根节点的rank[]值都是0，现在要更新xx，即xx成为了yy的子树  
            }                       //那一定要更新rank[xx]的值。本来rank[x]和rank[y]分别为相对xx跟yy  
        }                           //的性别，并且x跟y是新进入的节点，所以他们是异性。  
                                    //所以xx相对于yy的性别为!(rank[x]^rank[y])  
        if(re==1)  
            printf("Scenario #%d:\nSuspicious bugs found!\n\n",i);  
        else  
            printf("Scenario #%d:\nNo suspicious bugs found!\n\n",i);  
    }  
    return 0;  
}  

 

补充：软件开发 , C++ ,