<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 不是树
代码: