## Approach 1: DFS

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

## C++

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

class Solution {
public:
int minimumSemesters(int n, vector<vector<int>>& relations) {
vector<vector<int>> graph(n);
vector<State> state(n);
vector<int> depth(n, 1);

for (const auto& r : relations)
graph[r[0] - 1].push_back(r[1] - 1);

for (int i = 0; i < n; ++i)
if (hasCycle(graph, i, state, depth))
return -1;

return *max_element(begin(depth), end(depth));
}

private:
bool hasCycle(const vector<vector<int>>& graph, int u, vector<State>& state,
vector<int>& depth) {
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, depth))
return true;
depth[u] = max(depth[u], 1 + depth[v]);
}
state[u] = State::VISITED;

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

## JAVA

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

class Solution {
public int minimumSemesters(int n, int[][] relations) {
List<Integer>[] graph = new List[n];
State[] state = new State[n];
int[] depth = new int[n];
Arrays.fill(depth, 1);

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

for (int[] r : relations)

for (int i = 0; i < n; ++i)
if (hasCycle(graph, i, state, depth))
return -1;

return Arrays.stream(depth).max().getAsInt();
}

private boolean hasCycle(List<Integer>[] graph, int u, State[] state, int[] depth) {
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, depth))
return true;
depth[u] = Math.max(depth[u], 1 + depth[v]);
}
state[u] = State.VISITED;

return false;
}
}
``````

## Python

``````from enum import Enum

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

class Solution:
def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
graph = [[] for _ in range(n)]
state = [State.INIT] * n
depth = [1] * n

for u, v in relations:
graph[u - 1].append(v - 1)

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

state[u] = State.VISITING
for v in graph[u]:
if hasCycle(v):
return True
depth[u] = max(depth[u], 1 + depth[v])
state[u] = State.VISITED

return False

if any(hasCycle(i) for i in range(n)):
return -1
return max(depth)
``````

## Approach 2: Topology

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

## C++

``````class Solution {
public:
int minimumSemesters(int n, vector<vector<int>>& relations) {
int ans = 0;
vector<vector<int>> graph(n);
vector<int> inDegree(n);
queue<int> q;

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

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

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

return n == 0 ? ans : -1;
}
};
``````

## JAVA

``````class Solution {
public int minimumSemesters(int n, int[][] relations) {
int ans = 0;
List<Integer>[] graph = new List[n];
int[] inDegree = new int[n];

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

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

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

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

return n == 0 ? ans : -1;
}
}
``````

## Python

``````class Solution:
def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
ans = 0
graph = [[] for _ in range(n)]
inDegree = [0] * n

# build graph
for a, b in relations:
u = a - 1
v = b - 1
graph[u].append(v)
inDegree[v] += 1

# topology
q = deque([i for i, d in enumerate(inDegree) if d == 0])

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

return ans if n == 0 else -1
``````