1272 小希的迷宫.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

//无回路求不相交集合，用了并查集
//还要判断树的特性，是否连通 
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;

const int Max=100001;
int Parent[Max],Rank[Max];
bool flag;

inline int Find(int x)
{
    int temp=x;
    int root,w;
    
    while(Parent[x]!=0)   //搜寻根节点
        x=Parent[x];
    root=x;
    x=temp;
    while(Parent[x]!=0)  //压缩路径
    {
        w=Parent[x];
        Parent[x]=root;
        x=w;
    }
    return root;
}

inline int Union(int x,int y)
{
    int u,v;
    int root;
    
    u=Find(x);
    v=Find(y);
    if(u==v)
    {	
		flag=false;
		return -1;
	}
    if(Rank[u]<=Rank[v])
    {
        root=Parent[u]=v;
        if(Rank[u]==Rank[v])
            Rank[v]++;
    }
    else
        root=Parent[v]=u;
        
    return root;
}

int main()
{
	int x,y;
	int edge,point;
	
	flag=true;
	point=edge=0;
	while(scanf("%d %d",&x,&y)==2)
	{
		if(x==-1 && y==-1)
			break;
		if(x==0 && y==0)
		{
			if(flag && edge>=point-1)
				printf("Yes\n");
			else
				printf("No\n");
			flag=true;
			point=edge=0;
			memset(Parent,0,sizeof(Parent));
			memset(Rank,0,sizeof(Rank));
			continue;
		}
		
		edge++;
		if(Rank[x]==0 && Parent[x]==0)
			point++;
		if(Rank[y]==0 && Parent[y]==0)
			point++;
			
		if(flag)
			Union(x,y);
	}
	return 0;
}