http://acm.nyist.net/JudgeOnline/problem.php?pid=129
一个有向图入度为1的节点仅有一个，并且无环，则是一颗树。
#include<cstdio>
#include <cstring>
using namespace std;
const int MAXSIZE = 10002;
int pre[MAXSIZE]; //根节点i,pre[i] = -num,其中num是该树的节点数目;
//非根节点j,pre[j] = k,其中k是j的父节点
int Find(int x){//查找+非递归的路径压缩
int p = x;
while( pre[p] > 0 ) p = pre[p];
while( x != p ){
int temp = pre[x]; pre[x] = p; x = temp;
}
return x;
}
void Union(int r1, int r2){
int a = Find(r1); int b = Find(r2);
if( a == b ) return ;
//加权规则合并
if( pre[a] < pre[b] ){
pre[a] += pre[b]; pre[b] = a;
}
else {
pre[b] += pre[a]; pre[a] = b;
}
}
void Initi(void)
{
for( int i=0; i < MAXSIZE; ++i ) pre[i] = -1;
}
int treeEs[MAXSIZE];
int main(){
//freopen("1.txt","r",stdin);
int begin,end,flag=1,n=1;
Initi();
memset(treeEs,-1,sizeof(treeEs));
while(scanf("%d%d",&begin,&end))
{
if(begin==-1 && end==-1) break;
if(begin==0 && end==0){
int enternum=0;
for (int i=0;i<MAXSIZE;i++)
{
if(treeEs[i]==0) enternum++;
}
if(enternum>1) flag=0;
if(flag)
printf("Case %d is a tree.\n",n++);
else printf("Case %d is not a tree.\n",n++);
memset(treeEs,-1,sizeof(treeEs));
flag=1;
Initi();
}
else{
if(flag==0) continue;
if(Find(begin)==Find(end)) flag=0;
else{
if(treeEs[begin]<0) treeEs[begin]=0;
if(treeEs[end]<0) treeEs[end]=0;
treeEs[end]++;
Union(begin,end);
}
}
}
}
