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.執行結果