261.以图判树

付费题

给定从 0 到 n-1 标号的 n 个结点，和一个无向边列表（每条边以结点对来表示），请编写一个函数用来判断这些边是否能够形成一个合法有效的树结构。

示例 1：

输入: n = 5, 边列表 edges = [[0,1], [0,2], [0,3], [1,4]] 输出: true 示例 2:

输入: n = 5, 边列表 edges = [[0,1], [1,2], [2,3], [1,3], [1,4]] 输出: false

注意：你可以假定边列表 edges 中不会出现重复的边。由于所有的边是无向边，边 [0,1] 和边 [1,0] 是相同的，因此不会同时出现在边列表 edges 中。

一、并查集

对每条变的顶点a、b，首先测试连通性，若已连通说明将这条边添加会产生环，否则不会

# 并查集代码略
class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        uf = UnionFind(n)
        for a, b in edges:
            if uf.isConnected(a, b):	#若ab连通，则这条边不能加入，直接返回
                return False
            uf.union(a, b)	#否则将ab连通
        return uf.count == 1	#最后还要看连通分量是否为1，若不为1也不是树