A Bug's Life

23 31 22 31 34 21 23 4樣例輸出
Scenario #1:Suspicious bugs found!Scenario #2:No suspicious bugs found!
解題報(bào)告：種類(lèi)并查集。把性別相同的蟲(chóng)子放在同一個(gè)集合，然后每讀入一對(duì)蟲(chóng)子號(hào)，判斷它們?cè)诓辉谕患希趧t同性別，不在則繼續(xù)。
code：
#include<iostream>#include<stdio.h>#include<queue>#include<vector>#include<stack>#include<cstring>#include<algorithm>using namespace std;typedef long long ll;const int MAXN = 10005; /*結(jié)點(diǎn)數(shù)目上限*/int pa[MAXN];    /*pa[x]表示x的父節(jié)點(diǎn)*/int rank[MAXN];    /*rank[x]是x的高度的一個(gè)上界*/int gender[MAXN];  // 與i性別相反的蟲(chóng)子號(hào)/*創(chuàng)建一個(gè)單元集*/void make_set(int x){    pa[x] = x;    rank[x] = 0;    gender[x]=0;}/*帶路徑壓縮的查找*/int find_set(int x){    if(x != pa[x]){        pa[x] = find_set(pa[x]);    }    return pa[x];}/*按秩合并x，y所在的集合*/void union_set(int x, int y){    x = find_set(x);    y = find_set(y);    if(rank[x] > rank[y])/*讓rank比較高的作為父結(jié)點(diǎn)*/    {        pa[y] = x;    }    else    {        pa[x] = y;        if(rank[x] == rank[y])            rank[y]++;    }}int main(){  //  freopen("input.txt","r",stdin);    int t,m,n,k=1;    scanf("%d",&t);    while(t--){        scanf("%d%d",&m,&n);        for(int i=1;i<=m;i++){ //初始化            make_set(i);        }        int a,b,flag=1;        for(int i=0;i<n;i++){            scanf("%d%d",&a,&b);            if(!flag) //結(jié)果出來(lái)之后也要把數(shù)據(jù)讀完                continue;            if(find_set(a)==find_set(b)){  //判斷兩個(gè)蟲(chóng)子在不在同一個(gè)集合                flag=0;                continue;            }            if(gender[a]==0) gender[a]=b; //把性別相同的蟲(chóng)子放在同一個(gè)集合里            else union_set(gender[a],b);            if(gender[b]==0) gender[b]=a;            else union_set(gender[b],a);        }        if(k!=1)            printf("/n");        if(flag)            printf("Scenario #%d:/nNo suspicious bugs found!/n",k++);        else            printf("Scenario #%d:/nSuspicious bugs found!/n",k++);    }    return 0;}