#include <stdbool.h>
#include <stdlib.h>
// adjacency in CSR form: node u's neighbors are edges[start[u] .. start[u+1])
static bool dfs(const int *start, const int *edges, int *state, int node,
int *order, int *orderSize) {
if (state[node] == 1)
return false; // cycle
if (state[node] == 2)
return true;
state[node] = 1;
for (int e = start[node]; e < start[node + 1]; e++)
if (!dfs(start, edges, state, edges[e], order, orderSize))
return false;
state[node] = 2;
order[(*orderSize)++] = node;
return true;
}
int *findOrder(int numCourses, int **prerequisites, int prerequisitesSize,
int *prerequisitesColSize, int *returnSize) {
(void)prerequisitesColSize; // always 2
int *start = calloc(numCourses + 1, sizeof(int));
int *edges = malloc((prerequisitesSize ? prerequisitesSize : 1) * sizeof(int));
for (int i = 0; i < prerequisitesSize; i++)
start[prerequisites[i][0] + 1]++;
for (int u = 0; u < numCourses; u++)
start[u + 1] += start[u];
int *fill = malloc(numCourses * sizeof(int));
for (int u = 0; u < numCourses; u++)
fill[u] = start[u];
for (int i = 0; i < prerequisitesSize; i++)
edges[fill[prerequisites[i][0]]++] = prerequisites[i][1];
free(fill);
int *state = calloc(numCourses, sizeof(int)); // 0 = unvisited, 1 = on path, 2 = done
int *order = malloc(numCourses * sizeof(int));
*returnSize = 0;
for (int i = 0; i < numCourses; i++)
if (!dfs(start, edges, state, i, order, returnSize)) {
*returnSize = 0; // cycle: no valid order
break;
}
free(start);
free(edges);
free(state);
return order;
}
#include <vector>
using namespace std;
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites) {
vector<vector<int>> adjacency(numCourses);
for (const auto &p : prerequisites)
adjacency[p[0]].push_back(p[1]);
vector<int> state(numCourses, 0); // 0 = unvisited, 1 = on path, 2 = done
vector<int> order;
for (int i = 0; i < numCourses; i++)
if (!dfs(adjacency, state, i, order))
return {};
return order;
}
private:
bool dfs(const vector<vector<int>> &adjacency, vector<int> &state, int node,
vector<int> &order) {
if (state[node] == 1)
return false; // cycle
if (state[node] == 2)
return true;
state[node] = 1;
for (int next : adjacency[node])
if (!dfs(adjacency, state, next, order))
return false;
state[node] = 2;
order.push_back(node);
return true;
}
};
package graphs
func findOrder(numCourses int, prerequisites [][]int) []int {
adjacency := make([][]int, numCourses)
for _, p := range prerequisites {
adjacency[p[0]] = append(adjacency[p[0]], p[1])
}
state := make([]int, numCourses) // 0 = unvisited, 1 = on path, 2 = done
order := make([]int, 0, numCourses)
var dfs func(node int) bool
dfs = func(node int) bool {
if state[node] == 1 {
return false // cycle
}
if state[node] == 2 {
return true
}
state[node] = 1
for _, next := range adjacency[node] {
if !dfs(next) {
return false
}
}
state[node] = 2
order = append(order, node)
return true
}
for i := 0; i < numCourses; i++ {
if !dfs(i) {
return []int{}
}
}
return order
}
import java.util.ArrayList;
import java.util.List;
class Solution {
private int[] order;
private int orderSize;
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> adjacency = new ArrayList<>(numCourses);
for (int i = 0; i < numCourses; i++)
adjacency.add(new ArrayList<>());
for (int[] p : prerequisites)
adjacency.get(p[0]).add(p[1]);
int[] state = new int[numCourses]; // 0 = unvisited, 1 = on path, 2 = done
order = new int[numCourses];
orderSize = 0;
for (int i = 0; i < numCourses; i++)
if (!dfs(adjacency, state, i))
return new int[0];
return order;
}
private boolean dfs(List<List<Integer>> adjacency, int[] state, int node) {
if (state[node] == 1)
return false; // cycle
if (state[node] == 2)
return true;
state[node] = 1;
for (int next : adjacency.get(node))
if (!dfs(adjacency, state, next))
return false;
state[node] = 2;
order[orderSize++] = node;
return true;
}
}
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {number[]}
*/
var findOrder = function (numCourses, prerequisites) {
const adjacency = Array.from({ length: numCourses }, () => []);
for (const [course, pre] of prerequisites) adjacency[course].push(pre);
const state = new Array(numCourses).fill(0); // 0 = unvisited, 1 = on path, 2 = done
const order = [];
const dfs = (node) => {
if (state[node] === 1) return false; // cycle
if (state[node] === 2) return true;
state[node] = 1;
for (const next of adjacency[node]) if (!dfs(next)) return false;
state[node] = 2;
order.push(node);
return true;
};
for (let i = 0; i < numCourses; i++) if (!dfs(i)) return [];
return order;
};
from typing import List
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
adjacency: List[List[int]] = [[] for _ in range(numCourses)]
for course, pre in prerequisites:
adjacency[course].append(pre)
state = [0] * numCourses # 0 = unvisited, 1 = on path, 2 = done
order: List[int] = []
def dfs(node: int) -> bool:
if state[node] == 1:
return False # cycle
if state[node] == 2:
return True
state[node] = 1
for nxt in adjacency[node]:
if not dfs(nxt):
return False
state[node] = 2
order.append(node)
return True
if not all(dfs(i) for i in range(numCourses)):
return []
return order
impl Solution {
pub fn find_order(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> Vec<i32> {
let n = num_courses as usize;
let mut adjacency = vec![Vec::new(); n];
for p in &prerequisites {
adjacency[p[0] as usize].push(p[1] as usize);
}
let mut state = vec![0u8; n]; // 0 = unvisited, 1 = on path, 2 = done
let mut order = Vec::with_capacity(n);
for i in 0..n {
if !Self::dfs(&adjacency, &mut state, i, &mut order) {
return Vec::new();
}
}
order
}
fn dfs(adjacency: &[Vec<usize>], state: &mut [u8], node: usize, order: &mut Vec<i32>) -> bool {
if state[node] == 1 {
return false; // cycle
}
if state[node] == 2 {
return true;
}
state[node] = 1;
for &next in &adjacency[node] {
if !Self::dfs(adjacency, state, next, order) {
return false;
}
}
state[node] = 2;
order.push(node as i32);
true
}
}