323. Number of Connected Components in an Undirected Graph
Question: Number of Connected Components in an Undirected Graph Solution 想法：Connection 的話就是 Union & Find 可以參考 684. Redundant Connection 題， 概念一樣 最後計算 group 的時候，題目給定 n 個 node，所以一開始一定是 n 個 group， 每一次成功 union node1 & node2，就將 n 減 1。 Time Complexity: O(edges + n) class Solution : def countComponentsS ( self , n : int , edges : list[list[ int ]]) -> int : parent = [i for i in range (n)] rank = [ 1 ] * n def find_parent ( node ): p = parent[node] while p != parent[p]: parent[node] = parent[p] p = parent[parent[p]] return p def union ( n1 , n2 ): p1, p2 = find_parent(n1), find_parent(n2) if p1 == p2: return 0 elif rank[p1] >= rank[p2]: parent[p2] = p1 rank[p1] += rank[p2] else : parent[p1] = p2 rank[p2] += rank[p1] re...
