#### HDU 1325 – Is It A Tree? [并查集]

vjudge题目链接

1. 只有一个根结点
2. 不能成环
3. 每个节点的入度<=1
4. 任意两个节点有且仅有一条通路，即不能成为森林

#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 102400;
vector<pair<int, int> > v;
int par[maxn], vis[maxn];
void Init(){
for(int i = 0; i < maxn; ++i)
par[i] = i;
memset(vis, false, sizeof(vis));
v.clear();
}
int Find(int x){return x==par[x] ? x : par[x]=Find(par[x]); }

int main(){
int x, y, kase = 0; Init();
while(~scanf("%d%d", &x, &y)){
if(x < 0) return 0;
if(x == 0  && y == 0) {
bool ok = true;
for(int i = 0; i != v.size(); ++i){
int a = Find(v[i].first), b = Find(v[i].second);
if(a == b || b != v[i].second) {
ok = false;
break;
}
else par[b] = a;
}
if(ok) {
int cnt = 0;
for(int i = 0; i < maxn; ++i)
if(vis[i] && Find(i)==i)
++cnt;
if(cnt > 1) ok = false;
}
if(ok) printf("Case %d is a tree.\n", ++kase);
else printf("Case %d is not a tree.\n", ++kase);
Init();
}
else v.push_back(make_pair(x, y)), vis[x]=vis[y]=true;
}
return 0;
}