Java - Typical 3-color strategy to check if cycle exists - Analysis included


  • 0
    C
    public class Solution {
        /* Three status of nodes:
            1. unvisited --> the node has not been touched
            2. inProgress  --> the node has been touched, but traversal from it is not finished
            3. visited --> the node is clean, which means all descendants have been traversed.
        */
        private static final int UNVISTED = 0;
        private static final int INPROGRESS = 1;
        private static final int VISITED = 2;
    
        //Intuitive way to represent a graph: adjacency list
        private void createGraph(int numCourses, List<List<Integer>> nodes, int[][] prerequisites) {
            for(int i = 0; i < numCourses; i++) {
                nodes.add(new LinkedList<Integer>());
            }
            
            for(int[] prerequisite : prerequisites) {
                nodes.get(prerequisite[0]).add(prerequisite[1]);
            }
        }
        
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            //Step1 : create the graph based on the provided edges.
            List<List<Integer>> nodes = new ArrayList<List<Integer>>(numCourses);
            createGraph(numCourses, nodes, prerequisites);
            int[] status = new int[numCourses];
            
            //Step2 : DFS starting from each node.
            for(int i = 0; i < numCourses; i++) {
                if(!dfs(i, status, nodes)) {
                    return false;
                }
            }
            
            return true;
        }
        
        private boolean dfs(int sVertex, int[] status, List<List<Integer>> nodes) {
            //Here's the key point of 3-color strategy:
            //1. If node is VISITED, then it's clean, all descendants have been traversed.
            //2. If INPROGRESS node is traversed again, it means a cycle exists, no topological order exists.
            if(status[sVertex] == VISITED) {
                return true;
            } else if(status[sVertex] == INPROGRESS) {
                return false;
            }
            
            status[sVertex] = INPROGRESS;
            
            //Traverse all its neighbors
            for(int eVertex : nodes.get(sVertex)) {
                if(!dfs(eVertex, status, nodes)) {
                    return false;
                }
            }
            
            status[sVertex] = VISITED;
            
            return true;
        }
    }
    

    Time complexity: O(|V| + |E|), every node and edge will be traversed once.

    Space complexity: O(|V| + |E|), storing nodes and edges.


Log in to reply
 

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