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;}
新闻热点
疑难解答
