LeetCode - Algorithms - 207. Course Schedule

my exercises is to find solutions which can help me to understand these puzzle algorithms.

Problem

207. Course Schedule

scheduling problem with precedence constraints.

key

  • DAG: a digraph with no directed cycles.
  • A digraph has a topological order if and only if it is a DAG.
  • Is a given digraph a DAG ?
  • Depth-first search

Java

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
    	List<Edge> edges = new ArrayList<Edge>();
    	for(int i=0; i<prerequisites.length; i++) {
    		edges.add(new Edge(prerequisites[i][0],prerequisites[i][1]));
    	}
    	Graph graph = new Graph(edges, numCourses);
        return isDAG(graph, numCourses);        
    }

    private boolean isDAG(Graph graph, int N) {
  		boolean[] discovered = new boolean[N];

  		int[] departure = new int[N];

  		int time = 0;

  		for (int i = 0; i < N; i++)
  			if (discovered[i] == false)
  				time = DFS(graph, i, discovered, departure, time);

  		for (int u = 0; u < N; u++) {
  			for (int v : graph.adjList.get(u)) {
  				if (departure[u] <= departure[v])
  					return false;
  			}
  		}
  		return true;
	}

  private int DFS(Graph graph, int v, boolean[] discovered, int[] departure, int time) {
		discovered[v] = true;

		for (int u : graph.adjList.get(v)) {
			if (!discovered[u])
				time = DFS(graph, u, discovered, departure, time);
		}

		departure[v] = time++;

		return time;
	}
}

class Edge {
	int source, dest;

	public Edge(int source, int dest) {
		this.source = source;
		this.dest = dest;
	}
}

class Graph {
	List<List<Integer>> adjList = null;

	Graph(List<Edge> edges, int N) {
		adjList = new ArrayList<>(N);

		for (int i = 0; i < N; i++) {
			adjList.add(i, new ArrayList<>());
		}

		for (Edge edge : edges) {
			adjList.get(edge.source).add(edge.dest);
		}
	}
}

Submission Detail

  • 42 / 42 test cases passed.
  • Runtime: 5 ms, faster than 69.31% of Java online submissions for Course Schedule.
  • Memory Usage: 44.6 MB, less than 94.62% of Java online submissions for Course Schedule.

ref