My Java Solution


  • 0
    P

    I need to make it simpler

    public class Solution {
        boolean[] isVisited;
        boolean[] isInPath;
        
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            Graph myGraph = new Graph(numCourses);
            for (int i = 0; i < prerequisites.length; i++){
                myGraph.addEdge(prerequisites[i]);
            }
            
            return findBackEdges(myGraph);
        }
        
        private boolean findBackEdges(Graph g){
            isVisited = new boolean[g.V];
            isInPath = new boolean[g.V];
            for(Integer s : g.adj.keySet()){
                if (!isVisited[s]){
                    dfs(g, s);
                }
            }
            return !g.isCyclic;
        }
        
        private void dfs(Graph g, int u){
            isVisited[u] = true;
            isInPath[u] = true;
            if (g.adj.containsKey(u)) {
                for (Integer v: g.adj.get(u)){
                    if (isInPath[v]) g.isCyclic = true;
                    if (!isVisited[v]){
                        dfs(g, v);
                    }
                }
            }
            isInPath[u] = false;
        }
        
         public class Graph {
            int V;
            Map<Integer, List<Integer>> adj;
            boolean isCyclic;
            
            public Graph(int V){
                adj = new HashMap<Integer, List<Integer>>();
                this.V = V;
                isCyclic = false;
            }
            
            public void addEdge(int[] pair){
                if (adj.containsKey(pair[1])){
                    adj.get(pair[1]).add(pair[0]);
                } else {
                    List<Integer> v = new ArrayList<Integer>();
                    v.add(pair[0]);
                    adj.put(pair[1], v);
                }
            }
        }
    }

Log in to reply
 

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