POJ 2492 A Bug's Life(并查集)

http://poj.org/problem?id=2492

题意 :就是给你n条虫子,m对关系,每一对关系的双方都是异性的,让你找出有没有是同性恋的。

思路 :这个题跟POJ1703其实差不多,也是需要一个数组来存跟父亲节点的关系,需要两个集合来存是否有关系,在最后稍微变一下形就OK了。

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h> using namespace std; int pre[];//代表着父亲结点,如果D后边是a b,则pre[b]=a ;
int father[] ;//代表着这个点和父亲结点的关系,是属于同一类还是不同团伙
int m,n ; int find(int x)
{
int temp = pre[x] ;
if (pre[x] == x)
return x ;
pre[x] = find(pre[x]);
father[x] = father[x] == father[temp] ? : ;//等于0表示属于同一类
return pre[x];
} void unionn(int x,int y,int xx,int yy)
{
pre[xx] = yy ;
father[xx] = father[x] == father[y] ? : ;
}
int main()
{
int t ;
scanf("%d",&t) ;
int m,n ,kase = ;
while(t--)
{
scanf("%d %d",&n,&m) ;
for(int i = ; i <= n ; i++)
{
pre[i]=i;
father[i] = ;
}
bool flag = false ;
int a,b ;
for(int i = ; i <= m ; i++)
{
scanf("%d %d",&a,&b) ;
int aa = find(a),bb = find(b);
if(!flag)
{
if(aa != bb)
unionn(a,b,aa,bb) ;
else
{
if(father[a] == father[b])
flag = true ;
}
}
}
printf("Scenario #%d:\n",kase) ;
kase++ ;
if(flag)
printf("Suspicious bugs found!\n\n") ;
else printf("No suspicious bugs found!\n\n") ;
}
return ;
}
上一篇:2021-03-26


下一篇:(Python程序设计(第3版)第二章列表预习总结)