A low DFS based solution. Any suggestions?

  • 0

    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>());
    		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;
    		if (graph.containsKey(nodeIndex)) {
    			ArrayList<Integer> neighborList = graph.get(nodeIndex);
    			for (Integer neighbor : neighborList)
    				if (!dfs(neighbor))
    					return false;
    		return true;

Log in to reply

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