这道题我看楼上的都用的是并查集,但是我觉得应该不用并查集:
想要判断是否为一棵树,先要想想树的性质:
- 树的点数=树的边数+1
- 树是联通的
- 而且树上除根节点外每个节点的入度为1(因为除根节点外每个节点只有一个父亲)
只要满足以上三个条件就是树了
所以思路就出来了:
首先判断树的点数是否=树的边数+1,如果不等于就not掉
然后统计一下每个点的入度,如果入度$\ge2$就not掉
最后找到入度为0的节点(根节点),然后从那个点开始DFS,搜到一个节点就计数,如果搜到的节点数和实际点数不同,就说明不联通,也not掉
如果以上都符合,就说明可以,就yes掉就行
感觉上述做法很容易超时,我过了8/11的数据
确实,但是如果像我这种不会写并查集的蒟蒻来说还是能接受的......