本題為二分的並查集，其實只要在原先的並查集基礎上作一下變形。當然此題也還是有技巧的，我們可以對每個節點做個標記，若該節點與父親節點屬於同一類，則標記為,0，否則標記為1。但當我們合並兩棵樹時，可能會存在兩棵樹的標記所表達的意思完全相反，此時我們就要通過改變其中一棵樹根節點的標記，來保持合並之後的樹保持一致。 至於何時有同性戀發生，應該不難判斷了，若兩個節點屬於同一棵樹且屬於同一類則發生同性戀。 [cpp] #include<iostream> #include<cstdio> using namespace std; const int maxn=2005; int set[maxn],flag[maxn]; //set[i]記錄i的父親節點，flag[i]==0表示該節點的性別與父親節點相同，否則不相同 void init(int n) { for(int i=1;i<=n;i++) { set[i]=i; flag[i]=0; } } int find1(int x)//返回父親節點 { while(set[x]!=x) x=set[x]; return x; } int find2(int x)//返回0或1，判斷該節點與根節點是否一致 { int t=0; while(set[x]!=x) { t^=flag[x]; x=set[x]; } return t; } bool merge(int x,int y)//合並 { int f1=find1(x); int f2=find1(y); if(f1==f2) return false; set[f1]=f2; //如果兩棵樹定義有沖突，則使它們一致（此處通過改變flag[f1]） if(find2(x)==find2(y)) flag[f1]^=1; return true; } int main() { int t,n,m,a,b,C=1; bool state; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); init(n); state=true; while(m--) { scanf("%d%d",&a,&b); if(!state) continue; if(!merge(a,b)&&(find2(a)^find2(b))==0)//同一棵樹且性別相同的兩個節點 state=false; } printf("Scenario #%d:\n",C++); if(!state) printf("Suspicious bugs found!\n"); else printf("No suspicious bugs found!\n"); printf("\n");//每個樣例後面都換行，坑爹的地方 } return 0; }
