给定从 0 到 n-1 标号的 n 个结点,和一个无向边列表(每条边以结点对来表示),请编写一个函数用来判断这些边是否能够形成一个合法有效的树结构。
时间: 2024-02-16 08:59:53 浏览: 54
判断点在多边形内的函数
判断给定的边是否能够形成一个合法有效的树结构,可以使用并查集来解决。并查集是一种可以动态维护若干集合,并支持合并和查询是否在一个集合中的数据结构。
在本问题中,我们可以使用并查集来判断给定的边是否构成了一个环,如果构成环,则说明不是一棵有效的树结构。
具体实现如下:
```python
class UnionFind:
def __init__(self, n):
self.parent = [i for i in range(n)]
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False # 构成环
self.parent[root_x] = root_y
return True # 合并成功
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) != n - 1: # 边的数量不足以构成一棵树
return False
uf = UnionFind(n)
for u, v in edges:
if not uf.union(u, v):
return False # 构成环
return True
```
在上述代码中,我们首先判断边的数量是否足以构成一棵树,如果不足则直接返回 False。然后,我们创建一个并查集对象,对于每一条边,我们使用并查集来判断两个节点是否已经在同一个集合中,如果是,则说明这两个节点之前已经有了一条路径,现在再添加这条边就会形成环,因此无法构成一棵树,直接返回 False。如果不是,则将这两个节点合并到同一个集合中。
最后,如果遍历所有边后都没有返回 False,则说明给定的边能够形成一棵有效的树结构,返回 True 即可。
阅读全文