Leetcode 323.無向グラフの連結成分の数(python + cpp)
Leetcode 323 Number Connected Components An Undirected Graph Python Cpp
Leetcode323。無向グラフの連結成分の数
分析はコードコメントを参照
class Solution: def countComponents(self, n: int, edges: List[List[int]]) -> int: def unionfind(p1,p2): nonlocal count # find root of p1 while root[p1]!=p1: p1 = root[p1] # find root of p2 while root[p2]!=p2: p2 = root[p2] #if roots of p1 and p2 are identicle, meaning they have already been merged if root[p1]==root[p2]: return # merge them if not merged else: root[p1] = p2 count -= 1 # initially, we have n connected path count = n # store original roots root = [i for i in range(n)] # go through each node pair for edge in edges: unionfind(edge[0],edge[1]) return count
時間の複雑さ :少し混乱しています。メッセージを残してください
スペースの複雑さ :O(N)、Nはノード数