23 31 22 31 34 21 23 4樣例輸出Scenario #1:Suspicious bugs found!Scenario #2:No suspicious bugs found!解題報告：種類并查集。把性別相同的蟲子放在同一個集合，然后每讀入一對蟲子號，判斷它們在不在同一集合，在則同性別，不在則繼續。
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; /*結點數目上限*/int pa[MAXN]; /*pa[x]表示x的父節點*/int rank[MAXN]; /*rank[x]是x的高度的一個上界*/int gender[MAXN]; // 與i性別相反的蟲子號/*創建一個單元集*/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比較高的作為父結點*/ { 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) //結果出來之后也要把數據讀完 continue; if(find_set(a)==find_set(b)){ //判斷兩個蟲子在不在同一個集合 flag=0; continue; } if(gender[a]==0) gender[a]=b; //把性別相同的蟲子放在同一個集合里 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;}
新聞熱點
疑難解答
