1325 is it a tree.cpp

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

//类似1272,但是本题是有向图 
//但是注意1 2 3 2 0 0，除了无回路集合外，还得满足树的特性 
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;

const int Max=100001;
int Parent[Max];
bool exist[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;
	}

	root=Parent[v]=u;
        
    return root;
}

int main()
{
	int x,y,ncase;
	int edge,point;
	
	flag=true;
	point=edge=0;
	ncase=1;
	while(scanf("%d %d",&x,&y)==2)
	{
		if(x==-1 && y==-1)
			break;
		if(x==0 && y==0)
		{
			if(flag && edge>=point-1)
				printf("Case %d is a tree.\n",ncase);
			else
				printf("Case %d is not a tree.\n",ncase);
			flag=true;
			point=edge=0;
			ncase++;
			memset(Parent,0,sizeof(Parent));
			memset(exist,0,sizeof(exist));
			continue;
		}
		
		edge++;
		if(!exist[x])
		{	point++;exist[x]=true;}
		if(!exist[y])
		{	point++;exist[y]=true;}
			
		if(flag)
			if(Parent[y]!=0)
			{
				flag=false;
			}
			else 
				Union(x,y);
	}
	return 0;
}