A low DFS based solution. Any suggestions?


  • 0
    Z

    Hi all,

    I implement a dfs-based solution. But it took too much time. I think my solution should be a O(v + e) and I donot really understand why it is so slow.

    public class Solution {
        HashMap<Integer, ArrayList<Integer>> graph = new HashMap<Integer, ArrayList<Integer>>();
    	ArrayList<Integer> sortedList = new ArrayList<Integer>();
    	HashSet<Integer> visitedSet = new HashSet<Integer>();
    
    	public int[] findOrder(int numCourses, int[][] pre) {
    		int[] sortedOrder = {};
    		for (int i = 0; i < pre.length; i++) {
    			if (graph.containsKey(pre[i][0]) == false)
    				graph.put(pre[i][0], new ArrayList<Integer>());
    			graph.get(pre[i][0]).add(pre[i][1]);
    		}
    
    		for (int i = 0; i < numCourses; i++)
    			if (!dfs(i))
    				return sortedOrder;
    		
    		sortedOrder = new int[numCourses];
    		for (int i = 0; i < sortedList.size(); i++)
    			sortedOrder[i] = sortedList.get(i);
    		return sortedOrder;
    	}
    
    	private boolean dfs(int nodeIndex) {
    
    		if (sortedList.contains(nodeIndex))
    			return true;
    
        	if (visitedSet.contains(nodeIndex))
    			return false;
    
    		visitedSet.add(nodeIndex);
    		if (graph.containsKey(nodeIndex)) {
    			ArrayList<Integer> neighborList = graph.get(nodeIndex);
    			for (Integer neighbor : neighborList)
    				if (!dfs(neighbor))
    					return false;
    		}
    		sortedList.add(nodeIndex);
    		return true;
    	}
    }

Log in to reply
 

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