List<Integer> topologicalOrder(List<List<Integer>> graph) {
int[] indegree = new int[graph.size()];
for (List<Integer> edges : graph) for (int next : edges) indegree[next]++;
ArrayDeque<Integer> queue = new ArrayDeque<>();
for (int node = 0; node < graph.size(); node++) if (indegree[node] == 0) queue.add(node);
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
int node = queue.remove();
order.add(node);
for (int next : graph.get(node)) if (--indegree[next] == 0) queue.add(next);
}
return order;
}
def topological_order(graph: list[list[int]]) -> list[int]:
indegree = [0] * len(graph)
for edges in graph:
for nxt in edges:
indegree[nxt] += 1
queue = deque(node for node, degree in enumerate(indegree) if degree == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return order
def topologicalOrder(graph: Vector[Vector[Int]]): Vector[Int] =
val indegree = Array.fill(graph.length)(0)
for edges <- graph; next <- edges do indegree(next) += 1
val queue = scala.collection.mutable.Queue[Int]()
for node <- graph.indices do if indegree(node) == 0 then queue.enqueue(node)
val order = scala.collection.mutable.Buffer[Int]()
while queue.nonEmpty do
val node = queue.dequeue()
order += node
for next <- graph(node) do
indegree(next) -= 1
if indegree(next) == 0 then queue.enqueue(next)
order.toVector
std::vector<int> topologicalOrder(const std::vector<std::vector<int>>& graph) {
std::vector<int> indegree(graph.size());
for (const auto& edges : graph) for (int next : edges) indegree[next]++;
std::queue<int> queue;
for (int node = 0; node < graph.size(); node++) if (indegree[node] == 0) queue.push(node);
std::vector<int> order;
while (!queue.empty()) {
int node = queue.front();
queue.pop();
order.push_back(node);
for (int next : graph[node]) if (--indegree[next] == 0) queue.push(next);
}
return order;
}