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); } } } }