## Approach 1: DFS

• Time:O(|V| + |E|), where |V| = \texttt{numCourses} and |E| = |\texttt{prerequisites}|
• Space:O(|V| + |E|), where |V| = \texttt{numCourses} and |E| = |\texttt{prerequisites}|

## C++

``````enum class State { INIT, VISITING, VISITED };

class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> ans;
vector<vector<int>> graph(numCourses);
vector<State> state(numCourses);

for (const auto& p : prerequisites)
graph[p[1]].push_back(p[0]);

for (int i = 0; i < numCourses; ++i)
if (hasCycle(graph, i, state, ans))
return {};

reverse(begin(ans), end(ans));
return ans;
}

private:
bool hasCycle(const vector<vector<int>>& graph, int u, vector<State>& state,
vector<int>& ans) {
if (state[u] == State::VISITING)
return true;
if (state[u] == State::VISITED)
return false;

state[u] = State::VISITING;
for (const int v : graph[u])
if (hasCycle(graph, v, state, ans))
return true;
state[u] = State::VISITED;
ans.push_back(u);

return false;
}
};
``````

## JAVA

``````enum State { INIT, VISITING, VISITED }

class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
Deque<Integer> ans = new ArrayDeque<>();
List<Integer>[] graph = new List[numCourses];
State[] state = new State[numCourses];

for (int i = 0; i < numCourses; ++i)
graph[i] = new ArrayList<>();

for (int[] p : prerequisites)

for (int i = 0; i < numCourses; ++i)
if (hasCycle(graph, i, state, ans))
return new int[] {};

return ans.stream().mapToInt(i -> i).toArray();
}

private boolean hasCycle(List<Integer>[] graph, int u, State[] state, Deque<Integer> ans) {
if (state[u] == State.VISITING)
return true;
if (state[u] == State.VISITED)
return false;

state[u] = State.VISITING;
for (final int v : graph[u])
if (hasCycle(graph, v, state, ans))
return true;
state[u] = State.VISITED;

return false;
}
}
``````

## Python

``````from enum import Enum

class State(Enum):
INIT = 0
VISITING = 1
VISITED = 2

class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
ans = []
graph = [[] for _ in range(numCourses)]
state = [State.INIT] * numCourses

for v, u in prerequisites:
graph[u].append(v)

def hasCycle(u: int) -> bool:
if state[u] == State.VISITING:
return True
if state[u] == State.VISITED:
return False

state[u] = State.VISITING
if any(hasCycle(v) for v in graph[u]):
return True
state[u] = State.VISITED
ans.append(u)

return False

if any(hasCycle(i) for i in range(numCourses)):
return []

return ans[::-1]
``````

## Approach 2: Topology

• Time:O(|V| + |E|)
• Space:O(|V| + |E|)

## C++

``````class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> ans;
vector<vector<int>> graph(numCourses);
vector<int> inDegree(numCourses);
queue<int> q;

// build graph
for (const auto& p : prerequisites) {
const int u = p[1];
const int v = p[0];
graph[u].push_back(v);
++inDegree[v];
}

// topology
for (int i = 0; i < numCourses; ++i)
if (inDegree[i] == 0)
q.push(i);

while (!q.empty()) {
const int u = q.front();
q.pop();
ans.push_back(u);
for (const int v : graph[u])
if (--inDegree[v] == 0)
q.push(v);
}

return ans.size() == numCourses ? ans : vector<int>();
}
};
``````

## JAVA

``````class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<Integer> ans = new ArrayList<>();
List<Integer>[] graph = new List[numCourses];
int[] inDegree = new int[numCourses];

for (int i = 0; i < numCourses; ++i)
graph[i] = new ArrayList<>();

// build graph
for (int[] p : prerequisites) {
final int u = p[1];
final int v = p[0];
++inDegree[v];
}

// topology
Queue<Integer> q = IntStream.range(0, numCourses)
.filter(i -> inDegree[i] == 0)
.boxed()
.collect(Collectors.toCollection(ArrayDeque::new));

while (!q.isEmpty()) {
final int u = q.poll();
for (final int v : graph[u])
if (--inDegree[v] == 0)
q.offer(v);
}

if (ans.size() == numCourses)
return ans.stream().mapToInt(i -> i).toArray();
return new int[] {};
}
}
``````

## Python

``````class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
ans = []
graph = [[] for _ in range(numCourses)]
inDegree = [0] * numCourses
q = deque()

# build graph
for v, u in prerequisites:
graph[u].append(v)
inDegree[v] += 1

# topology
for i, degree in enumerate(inDegree):
if degree == 0:
q.append(i)

while q:
u = q.popleft()
ans.append(u)
for v in graph[u]:
inDegree[v] -= 1
if inDegree[v] == 0:
q.append(v)

return ans if len(ans) == numCourses else []
``````