Python Solution


  • 0
    J
    class Solution(object):
        def countComponents(self, n, edges):
            """
            :type n: int
            :type edges: List[List[int]]
            :rtype: int
            """
            adj_list = self.make_adj_list(n, edges)
            
            visited = set()
            
            connected_graphs = 0
            for node in range(n):
                if node not in visited:
                    connected_graphs += 1
                    self.search_subgraph(node, adj_list, visited)
            return connected_graphs
    
        def make_adj_list(self, n, edges):
            adj_list = {}
            for node in range(n):
                adj_list[node] = []
            
            for e in edges:
                adj_list[e[0]].append(e[1])
                adj_list[e[1]].append(e[0])
            return adj_list
        
        def search_subgraph(self, node, adj_list, visited):
            frontier = [node]
            
            while frontier != []:
                curr = frontier.pop()
                visited.add(curr)
                for neighbor in adj_list[curr]:
                    if neighbor not in visited:
                        frontier.append(neighbor)
        ```

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.