Leetcode 261
给定编号从 0 到 n - 1 的 n 个结点。给定一个整数 n 和一个 edges 列表，其中 edges[i] = [ai, bi] 表示图中节点 ai 和 bi 之间存在一条无向边。
如果这些边能够形成一个合法有效的树结构，则返回 true ，否则返回 false 。
示例 1：
image.png
输入: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
输出: true
示例 2:
image.png
输入: 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 <= ai, bi < n
ai != bi
不存在自循环或重复的边
经分析，此题题意就是构建一张图，然后判断此图是否存在环以及是否全连通。如果存在环或者不是全连通则不是树。判断图是否存在环和判断图是否全连通是需要背诵的基本dfs算法，问一问deepseek，让它把两个方法写出来即可。
# @param {Integer} n
# @param {Integer[][]} edges
# @return {Boolean}
def valid_tree(n, edges)
g = (0...n).to_h {|it| [it,[]]}
for edge in edges
g[edge[0]].push(edge[1])
g[edge[1]].push(edge[0])
end
!has_cycle_dfs(g) && fully_connected?(g)
end
def has_cycle_dfs(graph)
visited = {}
dfs = lambda do |node, parent|
visited[node] = :visiting
graph[node].each do |neighbor|
if !visited.key?(neighbor)
return true if dfs.call(neighbor, node)
elsif visited[neighbor] == :visiting && neighbor != parent
return true
end
end
visited[node] = :visited
false
end
graph.keys.each do |node|
if !visited.key?(node)
return true if dfs.call(node, nil)
end
end
false
end
def fully_connected?(adjacency_list)
return true if adjacency_list.empty?
visited = Array.new(adjacency_list.size, false)
dfs = lambda do |v|
visited[v] = true
adjacency_list[v].each do |u|
dfs.call(u) unless visited[u]
end
end
dfs.call(0)
visited.all?
end
