HDU 1829 A Bug's Life（种类并查集）

约定不等于承诺〃 2022-06-17 02:37 93阅读 0赞

> A Bug’s Life
> 
> Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
> Total Submission(s): 15003 Accepted Submission(s): 4879
> 
> Problem 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!

> 题意：检查一堆数据中是否有同性恋，找出主要矛盾是如果1喜欢2,2喜欢3，而1又喜欢3，则矛盾。找出出现类的的矛盾

> 题解：并查集维护与根节点的关系。同性别的合并在一个集合中，然后每次输入看u，v是否在同一个集合中

> 代码：

#include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <string>
    #include <cstdio>
    
    using namespace std;
    const int maxn = 2000 + 5;
    int f[maxn];
    int relation[maxn];//代表该节点与父节点的关系,1代表与父节点性别不同,反之即为0
    int a,b;
    void init(int len)
    {
        for(int i =0;i<=len;i++)
        {
            f[i] = i;
            relation[i] = 0;
        }
    }
    int find(int x)
    {
        if(x == f[x])
            return x;
        int tmp = find(f[x]);
        relation[x] = (relation[x] + relation[f[x]])%2;//根据儿子与父亲的关系和父亲与爷爷的关系推出儿子与爷爷的关系
        f[x] = tmp;
        return f[x];
    }
    void mix(int x,int y)
    {
        int fx = find(x);
        int fy = find(y);
        if(fx == fy)
            return;
            f[fx] = fy;
            relation[fx] = (relation[y] + relation[x] +1)%2;
            return;
    }
    int main()
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cout<<"Scenario #"<<i<<":"<<endl;
            cin>>a>>b;
            init(a);//初始化，使其父节点为自己
            int _x,_y;
            bool flag = false;
            for(int k=1;k<=b;k++)
            {
                cin>>_x>>_y;
                if(find(_x) == find(_y) && relation[_x] == relation[_y])//同性
                    flag = true;
                else mix(_x,_y);
            }
            if(flag)
                cout<<"Suspicious bugs found!"<<endl;
            else cout<<"No suspicious bugs found!"<<endl;
            cout<<endl;
    
        }
        return 0;
    }