Standard algorithm of detecting cycle in directed graph - Java, runtime 6m


  • 0
    R

    public class Solution {

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Graph g = new Graph(prerequisites, numCourses);
        return checkCycle(g, numCourses);
    }
    
    private class Graph {
        private ArrayList<Integer>[] neighbors;
        
        public Graph(int[][] edges, int numCourses) {
            neighbors = (ArrayList<Integer>[])new ArrayList[numCourses];
            for(int i = 0; i < neighbors.length; i++) {
                neighbors[i] = new ArrayList<Integer>();
            }
            for(int i = 0; i < edges.length; i++) {
                neighbors[edges[i][0]].add(edges[i][1]);
            }
        }
        
        public ArrayList<Integer> getNeighbors(int v) {
            return (ArrayList<Integer>)neighbors[v];
        }
    }
    
    public boolean checkCycle(Graph g, int numCourses) {
        boolean[] visited = new boolean[numCourses];
        boolean[] visiting = new boolean[numCourses];
        
        for(int i = 0; i < numCourses; i++){
        	if(dfs(g, i, numCourses, visited, visiting))
        		return false;
        }
        return true;
    }
    
    public boolean dfs(Graph g, int v, int numCourses, boolean[] visited, boolean[] visiting) {
        if(!visited[v]){
        	visited[v] = true;
            visiting[v] = true;
            
            ArrayList<Integer> neighbors = g.getNeighbors(v);
            for(Iterator<Integer> it = neighbors.iterator(); it.hasNext();) {
                Integer neighbor = (Integer)it.next();
                if(!visited[neighbor] && dfs(g, neighbor, numCourses, visited, visiting))
                    return true;
                else if(visiting[neighbor])
                    return true;
            }
    
    	}
        visiting[v] = false;
        return false;
    }
    

    }


Log in to reply
 

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