首页 > 代码库 > POJ 2492 A Bug's Life
POJ 2492 A Bug's Life
题意:给你一个n m,n代表有多少只昆虫,m代表2只给定的昆虫可以交配
要你来判断是否出现了同性的昆虫相交的情况
思路:并查集的一个小的应用。运用类别转移来做,详细请看代码,这个代码网上叫类别转移啊,发现新大陆了
#include<stdio.h> #include<string.h> int f[2005],link[2005]; int find(int x) { if(x!=f[x]) f[x]=find(f[x]); return f[x]; } void make(int x,int y) { x=find(x); y=find(y); if(x==y) return ; f[y]=x; } int main() { int a,b,i,n,m,flag,t,cnt=1; scanf("%d",&t); while(t--) { scanf("%d %d",&n,&m); for(i=1;i<=n;i++) { link[i]=0; f[i]=i; } flag=0; while(m--) { scanf("%d %d",&a,&b); if(flag) continue; int x,y; x=find(a); y=find(b); if(x==y) flag=1; if(link[x]==0&&link[y]==0) //如果2个数跟谁都还没有关系 { link[x]=y; //确定关系 link[y]=x; } else if(link[x]==0) { link[x]=y; make(x,link[y]); //将link[y]的父节点找出来,将x的值给f[y],只要再次出现x或是x的集合种的 } //那只虫,那么我们就找到了同类相交的情况 else if(link[y]==0) { link[y]=x; make(y,link[x]); } else { make(x,link[y]); make(y,link[x]); } } printf("Scenario #%d:\n",cnt++); if(flag) printf("Suspicious bugs found!\n\n"); else printf("No suspicious bugs found!\n\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。