0261：以图判树（★）

2015-09-18 约 259 字预计阅读 1 分钟次阅读

力扣第 261 题

题目

给定编号从 0 到 n - 1 的 n 个结点。给定一个整数 n 和一个 edges 列表，其中 edges[i] = [a_i, b_i] 表示图中节点 a_i 和 b_i 之间存在一条无向边。

如果这些边能够形成一个合法有效的树结构，则返回 true ，否则返回 false 。

示例 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

提示：

1 <= n <= 2000
0 <= edges.length <= 5000
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
不存在自循环或重复的边

分析

只要所有点连通且没有环，即是一棵树。用并查集判断即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


def validTree(self, n: int, edges: List[List[int]]) -> bool:
    def find(x):
        if f[x] != x:
            f[x] = find(f[x])
        return f[x]
    
    def union(x, y):
        f[find(x)] = find(y)
    
    if len(edges) != n-1:
        return False
    f = list(range(n))
    for u, v in edges:
        if find(u)==find(v):
            return False
        union(u, v)
    return True

40 ms

目录

0261：以图判树（★）

题目

分析

解答