Graph based Java DFS Solution


  • 0
    K
    1. Construct a graph from the given input.
    2. Detect if there are cycles in the graph. (https://www.youtube.com/watch?v=rKQaZuoUR4M)
    public class Solution {
        
        Set<Integer> white = new HashSet<>();
        Set<Integer> grey = new HashSet<>();
        Set<Integer> black = new HashSet<>();
        
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            Graph graph = new Graph(numCourses);
            for(int i=0;i<prerequisites.length;i++) {
                graph.addEdge(prerequisites[i][0], prerequisites[i][1]);
            }
            return detectCycles(graph, numCourses);
        }
        
        private boolean detectCycles(Graph graph, int numCourses) {
            int i = 0;
            while(i < numCourses) {
                white.add(i);
                i++;
            }
            for(int j=0;j<graph.edges.length;j++) {
                if(exploreChildren(graph, j) == -1) return false;
            }
            return true;
        }
        
        private int exploreChildren(Graph graph, int c) {
            List<Integer> l = graph.edges[c];
            white.remove(c);
            grey.add(c);
            if(l != null) {
                for(Integer i : l) {
                    if(black.contains(i)) continue;
                    if(grey.contains(i)) return -1;
                    if(exploreChildren(graph, i) == -1) return -1;
                    grey.remove(i);
                    black.add(i);
                }
            }
            grey.remove(c);
            black.add(c);
            return 1;
        }
    }
    
    class Graph {
        List<Integer>[] edges;
        public Graph(int numOfVertices) {
            edges = new LinkedList[numOfVertices];
        }
        public void addEdge(int in, int out) {
            if(edges[in] == null) {
                edges[in] = new LinkedList<>();
            }
            edges[in].add(out);
        }
    }
    

Log in to reply
 

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