Leetcode 261. 以图判树

1.题目基本信息

1.1.题目描述

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

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

1.2.题目地址

https://leetcode.cn/problems/graph-valid-tree/description/

2.解题方法

2.1.解题思路

并查集

2.2.解题步骤

并查集方法步骤

• 第一步，构建并查集，并将所有的节点添加到并查集中

• 第二步，遍历所有的边，将相关相连的点进行连接，如果边的两端都在同一个集合中，则代表存在环，直接返回false

• 第三步，如果图中无环，则只要并查集中的集合数为1就能保证图能构建成熟

DFS方法步骤

• 第一步，构建邻接表和访问状态（分为未访问、访问中、已访问）

• 第二步，构建递归函数。递归任务：返回node所在连通分量中是否有环

• 第三步，如果图中无环且只有一个连通分量则可以构建成树

3.解题代码

DFS版本代码

class Solution:# 判断无向图有无环：DFS+三色标记法def validTree(self, n: int, edges: List[List[int]]) -> bool:# 第一步，构建邻接表和访问状态（分为未访问、访问中、已访问）graph=[[] for _ in range(n)]for edge in edges:graph[edge[0]].append(edge[1])graph[edge[1]].append(edge[0])states=[0]*n    # 0表示未访问，1表示访问中，2表示已访问# 第二步，构建递归函数。递归任务：返回node所在连通分量中是否有环def dfs(node,parentNode):for subNode in graph[node]:if subNode==parentNode:continueif states[subNode]==1:return Trueelif states[subNode]==0:states[subNode]=1if dfs(subNode,node):return Truestates[node]=2return False# 第三步，如果图中无环且只有一个连通分量则可以构建成树states[0]=1return not dfs(0,-1) and all([states[i]==2 for i in range(n)])

并查集版本代码

# # ==> 并查集模板(附优化)
class UnionFind():def __init__(self):self.roots={}self.setCnt=0   # 连通分量的个数# Union优化:存储根节点主导的集合的总节点数self.rootSizes={}def add(self,x):if x not in self.roots:self.roots[x]=xself.rootSizes[x]=1self.setCnt+=1def find(self,x):root=xwhile root != self.roots[root]:root=self.roots[root]# 优化:压缩路径while x!=root:temp=self.roots[x]self.roots[x]=rootx=tempreturn rootdef union(self,x,y):rootx,rooty=self.find(x),self.find(y)if rootx!=rooty:# 优化:小树合并到大树上if self.rootSizes[rootx]<self.rootSizes[rooty]:self.roots[rootx]=rootyself.rootSizes[rooty]+=self.rootSizes[rootx]else:self.roots[rooty]=rootxself.rootSizes[rootx]+=self.rootSizes[rooty]self.setCnt-=1class Solution:# 并查集def validTree(self, n: int, edges: List[List[int]]) -> bool:# 第一步，构建并查集，并将所有的节点添加到并查集中uf=UnionFind()for i in range(n):uf.add(i)# 第二步，遍历所有的边，将相关相连的点进行连接，如果边的两端都在同一个集合中，则代表存在环，直接返回falsefor node1,node2 in edges:if uf.find(node1)!=uf.find(node2):uf.union(node1,node2)else:# 有环return False# 第三步，如果图中无环，则只要并查集中的集合数为1就能保证图能构建成熟return uf.setCnt==1

4.执行结果