Graph Valid Tree
给你 n 个节点，编号从 0 到 n-1，以及一个由无向边组成的列表 edges。每一对 [a, b] 都连接节点 a 和节点 b。
如果这些边能将所有 n 个节点组成一棵树，就返回 true：每个节点都能到达其他所有节点，并且不存在环。否则返回 false。
函数
- ninteger
- 节点数量，编号从 0 到 n-1
- edgesinteger-2d-array
- 无向边，每条边都是一对 [a, b]
- 返回值boolean
- 如果这些边将所有 n 个节点连接成一棵树，则为真；否则为假
约束条件
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [a, b]，其中0 ≤ a, b ≤ n-1且a ≠ b- 没有任何一条边会重复出现，无论方向如何。
示例
- 输入
- n = 5edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
- 输出
- true
- 解释
- 节点 0 连接到节点 1、2 和 3，节点 4 则连接到节点 1。4 条边将全部 5 个节点连接起来，且没有循环，因此这是棵树。
- 输入
- n = 5edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
- 输出
- false
- 解释
- 边
[1, 2]、[2, 3]和[1, 3]构成了循环 1、2、3、1。5 个节点上的 5 条边比树所能拥有的边多 1 条。
- 输入
- n = 4edges = [[0, 1], [1, 2], [2, 0]]
- 输出
- false
- 解释
- 有 3 条边，也就是
n-1，但它们构成了循环 0、1、2、0，而节点 3 一条边也没有。
进阶
当图不是树时，必须删除多少条边，并添加多少条边，才能使它变成树？你能否只遍历一次就把两者都数出来？
提示
逐个打开提示，每个都会多透露一点。
画几个不是树的小图。只有两种失败的方式：它们是什么？
图不符合要求的情况有两种：包含环，或者有些节点被孤立。一个有
n个节点的树恰好有n-1条边；而当边数恰好为n-1时，这两种情况总是同时出现。因此，先检查数量，再检查其中一种情况。让每个节点一开始都单独成组。对于每条边，检查它连接的两个端点是否已经属于同一组。如果是，这条边就会形成一个环；如果不是，就把这两组合并起来。并查集几乎可以在常数时间内回答这个问题。
题解
树是连通的，并且没有环。边数恰好为 n-1 时，这两个条件等价：当且仅当图中没有环时，图才是连通的。因此，先检查边数，然后搜索一次以判断图是否连通，或者让并查集捕捉连接两个已经连通的节点的边。
在每条边之前搜索路径
结果正确，但无法在最大的测试中运行完毕
思路
一次添加一条边。在添加 [u, v] 之前，从 u 出发，沿着目前已添加的边进行搜索。如果能到达 v，那么这条新边就构成了它们之间的第二条路径，并形成一个环，第二个示例中的 [1, 3] 就是这样。如果没有边形成环，那么这个图就是森林；最后从节点 0 开始搜索，就能判断它是否是一棵树。
每次检查都会搜索目前为止的整个图。对于一条有 5001 个节点、边按顺序到达的路径，搜索会访问 1 + 2 + ... + 5000 个节点，大约 1250 万个。
算法
- 先为每个节点创建一个空邻接表。
- 对于每条边
[u, v]，沿着目前已添加的边从u开始搜索。如果能到达v，则返回false。 - 否则，将这条边添加到两端节点的列表中。
- 最后，返回从节点 0 开始搜索是否能到达全部
n个节点。
def reachable(graph, start):
# Every node a search from start can reach, using the edges added so far.
seen = [False] * len(graph)
seen[start] = True
stack = [start]
while stack:
node = stack.pop()
for nxt in graph[node]:
if not seen[nxt]:
seen[nxt] = True
stack.append(nxt)
return seen
def validTree(n, edges):
graph = [[] for _ in range(n)]
for u, v in edges:
# A path from u to v already exists, so this edge closes a cycle.
if reachable(graph, u)[v]:
return False
graph[u].append(v)
graph[v].append(u)
# No cycle anywhere. A tree also needs every node reachable from node 0.
return all(reachable(graph, 0))数一数边，然后搜索一次
思路
从 n 个彼此独立的节点开始，逐条添加边。每条边要么连接两个组，使组的数量减少 1；要么落在同一个组内，形成一个环。要得到一个组，需要连接 n-1 次。因此，少于 n-1 条边无法连通图，多于 n-1 条边则必定会形成环：第二个示例中，5 个节点有 5 条边，仅根据数量就能判断它不符合要求。
恰好有 n-1 条边时，只有在每条边都连接两个组，也就是没有边形成环的情况下，图最终才会成为一个组。因此，数量正确后，只需检查连通性：从节点 0 开始搜索，必须能到达全部 n 个节点。第三个示例中，搜索只能到达 0、1 和 2。当 m = n-1 时，列表和搜索的开销为 O(n)。
算法
- 如果
edges.length不等于n-1，返回false。 - 构建邻接表，将每条边存储在它的两个端点下。
- 将节点 0 压入栈，并标记为已访问。
- 弹出节点，将所有尚未访问的邻居压入栈，并在压入时标记和计数。
- 返回计数是否等于
n。
def validTree(n, edges):
# A tree on n nodes has exactly n-1 edges.
if len(edges) != n - 1:
return False
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
# With n-1 edges, the graph is a tree exactly when it is connected.
seen = [False] * n
seen[0] = True
stack = [0]
reached = 1
while stack:
node = stack.pop()
for nxt in graph[node]:
if not seen[nxt]:
seen[nxt] = True
reached += 1
stack.append(nxt)
return reached == n统计边数和并查集
思路
并查集无需搜索，就能针对每条边判断是否形成环。每个节点一开始都属于自己的组。对于一条边 [u, v]，找到两端各自的根。根不同：这条边连接了两个部分，因此将它们合并。根相同：u 和 v 已经连通，这条边会形成一个环。当 n-1 条边都执行了合并后，n 个组最终会合并为一个：这就是一棵树。
两条规则可以缩短父节点链。合并时，将较小组的根挂到较大组的根下面，因此对于 10^4 个节点，没有一条链会超过 13 步。查找时，将经过的每个节点指向它的祖父节点。结合起来，m 次操作的时间复杂度为 O(m α(n))，其中 α 是反阿克曼函数，在这里最大为 4。空间复杂度为 O(n)。
算法
- 如果
edges.length不等于n-1，返回false。 - 为每个节点设置
parent[x] = x，并将组大小设为 1。 - 对于每条边
[u, v]，分别从u和v沿着父节点找到它们的根，并让经过的每个节点指向它的祖父节点。 - 如果根相同：返回
false。 - 如果根不同：将较小组的根连接到另一个组的根，并累加组的大小。
- 如果每条边都合并了两个组，返回
true。
def validTree(n, edges):
# A tree on n nodes has exactly n-1 edges.
if len(edges) != n - 1:
return False
parent = list(range(n)) # every node starts as its own group
size = [1] * n
def find(x):
# Walk up to the root, halving the path on the way.
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v in edges:
a, b = find(u), find(v)
# The two ends are already joined: this edge closes a cycle.
if a == b:
return False
# Hang the smaller group under the larger one.
if size[a] < size[b]:
a, b = b, a
parent[b] = a
size[a] += size[b]
# n-1 merges with no cycle turn the n groups into one.
return True
易错点和边界情况
- 只检查是否存在环。6 个节点上的 3 条独立边没有形成环，但它们将节点分成了 3 个部分。
- 只检查边的数量。第三个示例有
n-1条边，但循环 0, 1, 2 占用了连接节点 3 所需的边。 - 每条边只存储在一端。
[1, 0]也连接节点 0 和 1，因此从节点 0 开始搜索时会漏掉节点 1。 - 深度优先环检测没有跳过父节点。每条边都会直接连回你刚离开的节点，因此“遇到已访问的邻居”会在每棵树中触发。
- 在很长的路径上使用递归。由 5001 个节点组成的一条直线会产生 5000 层调用，超过 Python 默认的 1000 层限制；请使用显式栈。
常见问题3
Graph Valid Tree 的时间复杂度是多少？
使用深度优先搜索时，时间复杂度为 O(n + m)，其中 m 是边的数量；使用并查集时，时间复杂度为 O(n + m α(n))。两种方法都会先检查边的数量，因此边数不正确的图会在搜索前被拒绝。
为什么有 n 个节点的树有 n-1 条边？
从一个节点开始构建树，然后一次添加一个其他节点。每个新节点恰好通过一条边接入：没有边，它就会被孤立；有两条边，就会形成一个环。因此，n 个节点需要 n-1 条边。
如何检测无向图中的环？
使用并查集时，如果一条边的两个端点已经有相同的根节点，就会形成一个环。使用深度优先搜索时，环是指已访问过的邻居节点，且该节点不是你到达当前节点时经过的节点，因此你需要记录每个节点的父节点。并查集既不需要父节点，也不需要邻接表。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def validTree(n, edges):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
n = 5 edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
预期输出
true