http://acm.hdu.edu.cn/showproblem.php?pid=1272并查集练习，这是一道很典型的并查集问题，问题是判断图在连通的情况下是否有环。用并查集可以判断是否有环，但怎么判断连通呢？如果图的父节点不止一个则一定不连通，我们就看父节点个数。
#include <iostream>
using namespace std;
int parent[100002];
int UFfind(int i)
{
int j;
for(j=i;parent[j]>0;j=parent[j]);
while(j!=i)
{
parent[i]=j;
i=parent[i];
}
return j;
}
void UFunion(int i,int j)
{
int temp=parent[i]+parent[j];
if(parent[i]<parent[j])
{
parent[j]=i;
parent[i]=temp;
}
else
{
parent[i]=j;
parent[j]=temp;
}
}
int main()
{
int p,q,c,i,j,a,b;
while(scanf("%d%d",&p,&q)!=EOF,!(p==-1&&q==-1))
{
c=0;
a=0;
b=p;
memset(parent,-1,sizeof(parent));
while(!(p==0&&q==0))
{
if(parent[p]==-1 && parent[q]==-1) //如果是两个独立点合并，则根节点数加1
a++;
else
if(parent[p]!=-1 && parent[q]!=-1) //如果p,q不是同一颗树，合并后根节点数减1，
//如果是同一颗树，那么在后面的判断中会把c改为1，不影响后面的结果
a--; //这样做很巧妙
i=UFfind(p);
j=UFfind(q);
if(i!=j)
UFunion(i,j);
else
c=1;
scanf("%d%d",&p,&q);
}
if(!c && a==1 || b==0)
printf("Yes\n");
else
printf("No\n");
}
}posted on 2011-04-26 09:40
大大木马 阅读(812)
评论(3) 编辑 收藏 引用