這道題就是裸並查集，關鍵在於對不是樹幾種的判斷
1. 空樹是樹 2. 森林不是樹 3. 無環
或者從入度來看：1，無環；2，除了根，所有的入度為1，根入度為0；3，這個結構只有一個根，不然是森林了。
這道題本來暑假做的POJ 1308 但是HDU沒有過。在於空樹沒有考慮。
用並查集判斷有多少個森林注意編號是隨機的，不是次序....
/* input: 0 0 1 1 0 0 1 2 1 2 0 0 1 2 2 3 4 5 0 0 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 0 0 1 2 2 1 0 0 -1 -1 output: Case 1 is a tree. Case 2 is not a tree. Case 3 is not a tree. Case 4 is not a tree. Case 5 is not a tree. Case 6 is not a tree. */ #include#include #include #define inf 0x3ffffff #define maxn 10+100000 #define max(a,b) ((a)>(b)?(a):(b)) int N,M,K; int parent[maxn]; int vis[maxn]; int find(int *parent,int k) { if(parent[k]==-1) return k; parent[k]=find(parent,parent[k]); return parent[k]; } int main() { int i,j,again; int e,r,ans,ee,rr,cnt; int nn; memset(parent,-1,sizeof(parent)); memset(vis,0,sizeof(vis)); nn=ans=again=cnt=0; while(1) { if(again) { for(j=0,i=1;i<=nn;i++) { if(vis[i] && parent[i]==-1) j++; if(j>1) {ans=1;break;} } if(nn==0)ans=0; if(ans) printf("Case %d is not a tree.\n",++cnt); else printf("Case %d is a tree.\n",++cnt); ans=again=0; memset(parent,-1,sizeof(parent)); memset(vis,0,sizeof(vis)); } scanf("%d%d",&e,&r); nn=max(nn,max(e,r)); if(e<0 && r<0) break; if(e==0 && r==0 ) {again=1;continue;} vis[r]=vis[e]=1; if(ans==1) continue; ee=find(parent,e); rr=find(parent,r); if(r!=rr || rr==ee) ans=1; parent[rr]=ee; } return 0; }
