天天看点

poj 1308 Is It A Tree?

<a target="_blank" href="http://poj.org/problem?id=1308">点击打开链接poj 1308</a>

思路:并查集

分析:如果是一棵树,那么就只能有唯一的一个根节点。所以我们只要在输入的时候判断两个元素能否合并即可,如果输入的两个元素的根节点相同肯定是不满足的,其它还有“空树”“森林”都不算是树。所以最后还要判断一下是否是森林还是树。注意句子末尾有个“.”

输入的边可能是自环,这个是一个trick

注意以下数据

1: 0 0 空树是一棵树。

2: 1 1 0 0 不是树 1 和 1的根据点相同

3: 1 2 1 2 0 0 不是树,第二个开始1 和 2的根节点相同不是树

4: 1 2 2 3 4 5 不是树  森林不算是树

5: 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1  最后的9 和1根节点相同不是树

6: 1 2 2 1 0 0 不是树

代码: