2685. 统计完全连通分量的数量
Leetcode 721 (借助AI做题第三弹）
# @param {Integer} n
# @param {Integer[][]} edges
# @return {Integer}
def count_complete_components(n, edges)
g = (0...n).to_h { |it| [it, []] }
edges.each do |e|
g[e[0]].push(e[1])
g[e[1]].push(e[0])
end
m = []
g.each_pair do |k, v|
m << [k].concat(v)
end
r = find_connected_components(m)
cnt = 0
r.each do |r1|
g1 = {}
r1.each do |r2|
g1[r2] = g[r2]
end
m = g1.values.map { |it| it.length }.sum
if m == (g1.length - 1) * g1.length
cnt += 1
end
end
cnt
end
def find_connected_components(adjacency_list)
return [] if adjacency_list.empty?
visited = {}
components = []
dfs = lambda do |v, component|
visited[v] = true
component << v
adjacency_list.each_with_index do |neighbors, index|
if neighbors.include?(v)
neighbors.each do |u|
dfs.call(u, component) unless visited[u]
end
end
end
end
adjacency_list.flatten.uniq.each do |v|
unless visited[v]
component = []
dfs.call(v, component)
components << component
end
end
components
end
