# HDU-1325 简单图论(树的性质)
## [HDU-1325](http://acm.hdu.edu.cn/showproblem.php?pid=1325)
## 分析
根据树的性质(其实题目也说了), **一个树里一个节点入度为0(为根), 其他节点入度都为1.**
即这样的情况不是一棵树:
进一步思考有没有满足这一条件的反例呢? 当然有了:
> 然而, 此题数据实在太薄. 根本没有考虑这种情况的也能AC... 因此这里写的是除了能A题之外更加健壮的方法.
解决方法是: **使用并查集判断整个图是否全连通(无向图形式).**
另外并查集是可以用来判环(无用边)的, 网上题解很多是这样写的. 但其实在这里, 根据树的定义, **判断节点入度(0\*1+1\*n) + 判断全连通**, 这已经是无环的充分条件了.
## 代码
注意处理输入数据会比较繁琐.
```cpp
// -------------- GLOBAL ----------------
#define makeNode \
maxn = max(maxn, max(m, n)); \
exist[n] = exist[m] = true; \
++in[m];
bool exist[10086]; // 节点不一定连续
int in[10086]; // 记录入度
int setTree[10086];
int maxn = -INF;
bool flag;
// -------------- FUNC ----------------
int find(int x) { return x == setTree[x] ? x : setTree[x] = find(setTree[x]); }
// -------------- MAIN ----------------
int main() {
ios_base::sync_with_stdio(false);
int cnt = 0;
int n, m; // 从1开始
while (~INI(n) && ~INI(m) && n >= 0 && m >= 0) {
flag = true; // 默认为true(单节点树或空树)
if (n || m) { // 不是空树
maxn = -INF;
fill0(in);
fill0(exist);
F0(i, 10086) {
setTree[i] = i;
}
makeNode;
setTree[n] = m;
// 读入数据
while (~INI(n) && ~INI(m) && n && m) {
// 判断条件已经充分了, 没必要判环
// 如果加了这句反而会导致接下来判断全连通出问题
// if (!flag) continue;
makeNode;
int a = find(n);
int b = find(m);
if (a == b) { // 出现无用边
// flag = false;
continue;
}
setTree[a] = b;
}
// if (flag) {
bool hasIn0 = false;
int initSet = find(maxn);
F1(i, maxn) {
if (exist[i] && !in[i]) { // 入度为0的节点有且只能有一个(根)
if (hasIn0) { // 多了
flag = false;
break;
}
hasIn0 = true; // 正好
}
if (exist[i] && in[i] > 1) { // 入度>1的节点不能有
flag = false;
break;
}
if (exist[i] && find(i) != initSet) { // 不全连通可不行啊!
flag = false;
break;
}
}
if (!hasIn0) { // 少了
flag = false;
}
// }
}
// 输出结果
printf("Case %d is ", ++cnt);
if (flag)
printf("a tree.\n");
else
printf("not a tree.\n");
}
return 0;
}
```
![]()