leetcode-directed graph

207. Course Schedule.py

class Solution:
    """
    Thought Process:
        The problem come down to find whether directed graphs is cyclic or not.
            -prerequisites is a edge list
            -each course is a node
        DFS:
            step1: convert edge list into adjacent list since it's directed graph 
            step2: We iterate all nodes. For each node, we do dfs search.
                If during the search, we meet the node who's visiting, it means cycle happens.
                The difference between find cycle in undirected graph is we require 3 states of node instead of 2
                    0: not visited yet
                    1: visiting
                    2: visited already
        BFS+Indegree array:
            Idea: node with zero indegree means this course we don't need any prerequisites.
            step1: create graph and indegree array
            step2: put node with zero indegree into q
            step3: do bfs, during the search, we reduce the indegree of neighbor node(remove the edge from the graph), if indegree of nei becomes zero, we put into the queue.
            last step: to check if sum of indegree is 0. 0 means no edge left=>no cycles=> topoligical exists [algorithm guarantee]
    For example,
    n=2, 1->0 
    
    n=5, 3->4->0->2->1
    """
    def canFinish(self, n: int, edges: List[List[int]]) -> bool:
        """
        Problem formulation:
            The problem could be formulate as finding cycle in directed graphs.
        
        Using DFS to find cycle
        T:O(n) because each node only be visited once.
        """
        graph = collections.defaultdict(list)
        for a, b in edges:
            graph[a].append(b)
            
        def dfs(n, visit, graph):
             """to detect cycle in directed graph. During the search, we visit the node whose state is visiting, return True. Otherwise, return False
             Note:
                There's 3 states of node:
                    0:has not visited yet
                    1:visting
                    2:visited already
             """
            if visit[n] == 2:
                # we stop search if the node is visted already
                return False
            if visit[n] == 1:
                return True
            # mark this node visiting
            visit[n] = 1
            for nei in graph[n]:
                if dfs(nei, visit, graph):
                    return True
            # we mark this node visited already, after visited all neighbors of the node
            visit[n] = 2
            return False
        
        visit = [0 for _ in range(n)]
        for i in range(n):
            if dfs(i, visit, graph):
                return False
        return True
    
    def canFinish(self, n: int, edges: List[List[int]]) -> bool:
        """
        Problem formulation:
            The problem could be formulate as finding cycle in directed graphs.
            
        Using bfs with help of indegree array to find cycle
            
        Step1:
            1. we start exploring nodes w zero indegrees(because there'e won't be another edge coming to the node)
            2. start exploring neibor of this node(that's bfs), during the search, we reduce the indegree of neighbor node, if indegree of nei becomes zero, we put into the queue
            3. if number of counts we put into the queue eauql to total number of nodes means no cycle aka wheter sum of indegree array is zero or not
            
        Note: 
            1.indegree is zero means no coming edge to this node/ no dependencies
            2. So, afte bfs, for those node whose indegree is not zero, means there's always an existing edge to come back to this node. It represent there's a cycle.
            
        T:O(n+m)
        S:O(n+m)
        """
        graph = collections.defaultdict(list)
        # step1: calcalate indegree of each node
        indegree = [0 for _ in range(n)]
        for a, b in edges:
            graph[b].append(a)
            indegree[a] += 1
        # step2: bfs starting from node with 0 indegree and during the search, put the node w 0 indegree
        q = collections.deque([i for i in range(n) if indegree[i] == 0])
        count = len(q)
        while len(q) != 0:
            cur_node = q.popleft()
            for nei in graph[cur_node]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    count += 1
                    q.append(nei)
        return count == n
    
    def canFinish(self, n: int, edges: List[List[int]]) -> bool:
        """
        DFS:
        T:O(n+m)
        S:O(n+m)
        """
        # step1: convert edge list into adjacent list since it's directed graph
        graph = collections.defaultdict(list)
        for a, b in edges:
            graph[b].append(a) # graph[a].append(b) works fine also.
            
        visited = [0 for _ in range(n)]
        for i in range(n):
            if self.dfs(i, visited, graph):
                return False
        return True
    
    def dfs(self, cur, visited, graph):
        """to detect cycle in directed graph. During the search, we visit the node whose state is visiting, return True. Otherwise, return False"""
        if visited[cur] == 2:
            return False
        if visited[cur] == 1:
            return True
        # mark this node visiting
        visited[cur] = 1
        for nei_node in graph[cur]:
            if visited[nei_node] == 2:
                continue
            if self.dfs(nei_node, visited, graph):
                # detect cycle
                return True
        visited[cur] = 2
        return False
    
    def canFinish(self, n: int, edges: List[List[int]]) -> bool:
        """
        BFS + indegree
        T:O(n+m)
        S:O(n+m) +O(n)
        """
        graph = collections.defaultdict(list)
        # step1: calcalate indegree of each node
        indegree = [0 for _ in range(n)] #[1,1,1,0,1]
        for a, b in edges:
            graph[b].append(a)
            indegree[a] += 1 # indegree=[]
        # step2: bfs starting from node with 0 indegree and during the search, put the node w 0 indegree
        q = collections.deque([i for i in range(n) if indegree[i]==0]) #[3]
        while len(q) != 0:
            cur_node = q.popleft() # 3, 4, 0, 2, 1
            for nei in graph[cur_node]: 
                indegree[nei] -= 1 # nei=4, nei=0, nei=2, nei=1
                if indegree[nei] == 0:
                    q.append(nei)
        return sum(indegree) == 0 # no cycles