poj-2492- A Bug's Life

poj-2492- A Bug's Life

這個題題意很好理解：輸入樣例數T，然後每組數據首先輸入bug的個數n和m，bug編號為1——n！然後接下來輸入m組互為異性的bug的編號a和b，然後要求我們判斷這組數據裡是否存在一組同性的bug，與給出的數據矛盾，然後輸出對應結果；如果不存在，則輸出另外一種結果！

題解：這道題使用並查集即可，每次處理a和b之前需要判斷一下a和b之前是否已經和其它的異性bug交配過！然後每次處理完a和b之後判斷a和b是否是屬於樹的同一條分支的，如果是則證明a和b是同性bug！

代碼如下：

#include
#include
#include
using namespace std;
int yix[2014],f[2014];
void init(int n)
{
    for(int i=1; i<=n; i++)
    {
        f[i]=i;
        yix[i]=0;
    }
}
int find(int x)
{
    return f[x]==x?x:find(f[x]);
}
void unity(int a,int b)
{//合並同性的bug
    int x=find(a);
    int y=find(b);
    if(x!=y)
        f[x]=y;
}
int main()
{
    int T;
    cin>>T;
    for(int i=1; i<=T; i++)
    {
        bool tx_istrue=false;
        int n,m,a,b;
        cin>>n>>m;
        init(n);
        while(m--)
        {
            //如果yix[num]不為0的話表示num肯定與編號為yix[num]的異性bug交配過！
            cin>>a>>b;
            if(!yix[a]&&!yix[b])
            {
                yix[a]=b;//如果這兩只bug前面都沒有出現過，
                yix[b]=a;//則標記數組分別標記對方為異性!
            }
            else if(!yix[a]&&yix[b])
            {
                yix[a]=b;
                unity(a,yix[b]);//編號為a的bug肯定與編號為yix[b]的bug同性！
            }
            else if(yix[a]&&!yix[b])
            {
                yix[b]=a;
                unity(b,yix[a]);//編號為b的bug肯定與編號為yix[a]的bug同性！
            }
            else
            {//此處即我上面所說的判斷，在這表明a和b之前都分別與編號為yix[a]和yix[b]的異性bug交配過！
                unity(yix[a],b);
                unity(yix[b],a);
            }
            if(find(a)==find(b))
                tx_istrue=true;//每輸入一次就就行一次判斷，判斷a和b是否是同性！
        }
        printf("Scenario #%d:\n",i);
        if(tx_istrue)
            printf("Suspicious bugs found!\n");
        else
            printf("No suspicious bugs found!\n");
        printf("\n");

    }
    return 0;
}