学步园

并查集~~~

判断图是否连通且无回路

待连接的两点如果祖先节点相同，那么就构成回路

#include<stdio.h>
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
int father[100001],vis[100001],ans;
int findfather(int a){
	if(father[a]!=a)
		father[a]=findfather(father[a]);
	return father[a];
}
void merge(int a,int b){
	int x,y;
	x=findfather(a);
	y=findfather(b);
	if(x!=y)father[x]=y;
	else ans=0;        
}
int main()
{
	int a,b,mini,maxi,cnt,i,x,y;
	while(scanf("%d%d",&a,&b),a!=-1){
		if(a==0)              //到现在我也不明白为啥0，0时是Yes，不是No
		{
			printf("Yes/n");continue;
		}
		for(i=1;i<=100000;i++){
			vis[i]=0;father[i]=i;
		}
		vis[a]=vis[b]=1;
		mini=min(a,b);
		maxi=max(a,b);
		merge(a,b);
		ans=1;
		while(scanf("%d%d",&a,&b),a+b)    //看是否存在回路
		{
			x=min(a,b),y=max(a,b);
			if(x<mini) mini=x;
			if(y>maxi) maxi=y;merge(a,b);
			vis[a]=vis[b]=1;
		}
		for(cnt=0,i=mini;i<=maxi;i++)     //看图是否连通
		{
			if(father[i]==i && vis[i])cnt++;
			if(cnt>1)       //连通图中只有根节点的父节点是自身，cnt应该是1
			{
				ans=0;break;
			}
		}
		if(ans) printf("Yes/n");
		else printf("No/n");
	}
	return 0;
}