leetcode-graph

323. Number of Connected Components in an Undirected Graph.py

class Solution:
    """
    PC:
        Can I assume that no duplicate edges will appear in edges
    """
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        """
        Given n nodes and edge list of undirected graph, to find number of connected components.
        
        Note:
          In this question, we learn 
            1.what's connected graph.
            2.what's component of graph.
          
        Approach-DFS:
            
        Start iterating through the nodes in the graph and always starting a DFS search on it if the current node does not belong to any component yet( not visited yet). 
        Number of times we doing dfs on this graph equal to number of connected componenets in the graph.
        
        T: O(m+n), where n is number of nodes and m is number of edges because the algorithm processes each node and edge once.
        S: O(n)
        
        Reference:
            https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/discuss/77638/Python-DFS-BFS-Union-Find-solutions
        """
        def dfs(n, graph, visited):
            if visited[n]:
                # the search terminates because it has visited all nodes in the graph.
                return
            visited[n] = True
            for nei_node in graph[n]:
                dfs(nei_node, graph, visited)
                
        if len(edges) == 0:
            return n
        # conver edge list into adjacency list
        graph = collections.defaultdict(list)
        for edge in edges:
            n1, n2= edge[0], edge[1]
            graph[n1].append(n2)
            graph[n2].append(n1)
        # maintains an array that keeps track of the visited nodes.
        visited = [False] * n # Initially, each array value is false, and when the search arrives at node s, the value of visited[s] becomes true.
        ans = 0
        for i in range(n):
            if not visited[i]:
                dfs(i, graph, visited)
                ans += 1
        return ans
    
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        """
        Approach-BFS:
            
        Start iterating through the nodes in the graph and always starting a bfs search on it if the current node does not belong to any component yet( not visited yet). 
        Number of times we doing bfs on this graph equal to number of connected componenets in the graph.
        
        T: O(m+n), where n is number of nodes and m is number of edges because the algorithm processes each node and edge once.
        S: O(n)
        """
        if len(edges) == 0:
            return n
        # conver edge list into adjacency list
        graph = collections.defaultdict(list)
        for edge in edges:
            n1, n2= edge[0], edge[1]
            graph[n1].append(n2)
            graph[n2].append(n1)
        
        def bfs(node, graph, visited):
            # queue
            q = collections.deque([node])
            while len(q) != 0:
                cur_node = q.popleft()
                for nei in graph[cur_node]:
                    if visited[nei]:
                        continue
                    visited[nei] = True
                    q.append(nei)
                    
        visited = [False for _ in range(n)]
        ans = 0
        for i in range(n):
            if not visited[i]:
                bfs(i, graph, visited)
                ans += 1
        return ans
    
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        """
        DFS
        """
        g = collections.defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        
        nb_components = 0
        visited = [False for _ in range(n)]
        for node in range(n):
            if not visited[node]:
                self.dfs(node, visited, g)
                nb_components+=1
        return nb_components
    
    def dfs(self, cur, visited, graph):
        visited[cur] = True
        for nei in graph[cur]:
            if visited[nei]:
                continue
            self.dfs(nei, visited, graph)
            
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        """
        BFS
        """
        g = collections.defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        
        nb_components = 0
        visited = [False for _ in range(n)]
        for node in range(n):
            if not visited[node]:
                self.bfs(node, visited, g)
                nb_components+=1
        return nb_components
    
    def bfs(self, node, visited, graph):
        q = collections.deque([node])
        while q:
            cur = q.popleft()
            visited[cur] = True
            for nei in graph[cur]:
                if visited[nei]:
                    continue
                q.append(nei)