7ms Java DFS O(V+E) solution


  • 0
    C

    Adjacency list structure used to construct the graph.
    DFS algorithm with saved call-stack for cycle detection.

    public class Solution {

    private boolean[] marked;
    private boolean[] onStack;
    private boolean isDAG=true;
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
    
    	graph courses=new graph(numCourses,prerequisites);
    	marked=new boolean[numCourses];
    	onStack=new boolean[numCourses]; // saves the call stack
        
    	for (int i=0;i<numCourses;i++){
    		if (!marked[i])
    			dfs(courses,i);
    	}
    	
        return isDAG;
    }
    
    
    	
    	private void dfs(graph G, int v){
    		//dfs from source vertex v
    		marked[v]=true;
    		onStack[v]=true;
    		
    
    		for(int w:G.adj(v)){
    			if (!marked[w]) dfs(G,w);
    			else if (onStack[w]) {
    				isDAG=false;
    				return;
    			}
    		}
    		
    		onStack[v]=false;
    	}
    
    
    public class graph{
    	private ArrayList<Integer>[] adjacent; // adjacency list as graph data structure
    	
    	public graph(int numCourses, int[][] prerequisites){
    		//initialization
    		adjacent=(ArrayList<Integer>[]) new ArrayList[numCourses];
    	    for (int i=0;i<numCourses;i++){
    	    	adjacent[i]=new ArrayList<Integer>();
    	    }	
    	    
    	    for (int i=0;i<prerequisites.length;i++){
    	    	adjacent[prerequisites[i][1]].add(prerequisites[i][0]);
    	    }
    	}
    	
    	public Iterable<Integer> adj(int i){
    		return adjacent[i];
    	}
    }
    
    public static void main(String[] args){
    	int num=2;
    	int[][] a=new int[][]{{1,0}};
    	
    	Solution s=new Solution();
    	boolean result=s.canFinish(num,a);
    	System.out.println(result);
    	
    }
    

    }


Log in to reply
 

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