// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
// indeg[v] = how many prerequisites v still has (incoming edges).
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
// indeg[v] = how many prerequisites v still has (incoming edges).
n := len(graph)
indeg := make([]int, n)
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
// indeg[v] = how many prerequisites v still has (incoming edges).
n := len(graph)
indeg := make([]int, n)
// Count them: every edge u -> v adds one to v's in-degree.
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
// indeg[v] = how many prerequisites v still has (incoming edges).
n := len(graph)
indeg := make([]int, n)
// Count them: every edge u -> v adds one to v's in-degree.
for _, edges := range graph {
for _, v := range edges {
indeg[v]++
}
}
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
// indeg[v] = how many prerequisites v still has (incoming edges).
n := len(graph)
indeg := make([]int, n)
// Count them: every edge u -> v adds one to v's in-degree.
for _, edges := range graph {
for _, v := range edges {
indeg[v]++
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
// indeg[v] = how many prerequisites v still has (incoming edges).
n := len(graph)
indeg := make([]int, n)
// Count them: every edge u -> v adds one to v's in-degree.
for _, edges := range graph {
for _, v := range edges {
indeg[v]++
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
queue := []int{}
for v := 0; v < n; v++ {
if indeg[v] == 0 {
queue = append(queue, v)
}
}
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
// indeg[v] = how many prerequisites v still has (incoming edges).
n := len(graph)
indeg := make([]int, n)
// Count them: every edge u -> v adds one to v's in-degree.
for _, edges := range graph {
for _, v := range edges {
indeg[v]++
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
queue := []int{}
for v := 0; v < n; v++ {
if indeg[v] == 0 {
queue = append(queue, v)
}
}
// Output a ready node.
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
// indeg[v] = how many prerequisites v still has (incoming edges).
n := len(graph)
indeg := make([]int, n)
// Count them: every edge u -> v adds one to v's in-degree.
for _, edges := range graph {
for _, v := range edges {
indeg[v]++
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
queue := []int{}
for v := 0; v < n; v++ {
if indeg[v] == 0 {
queue = append(queue, v)
}
}
order := []int{}
for len(queue) > 0 {
// Output a ready node.
node := queue[0]
queue = queue[1:]
order = append(order, node)
}
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
// indeg[v] = how many prerequisites v still has (incoming edges).
n := len(graph)
indeg := make([]int, n)
// Count them: every edge u -> v adds one to v's in-degree.
for _, edges := range graph {
for _, v := range edges {
indeg[v]++
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
queue := []int{}
for v := 0; v < n; v++ {
if indeg[v] == 0 {
queue = append(queue, v)
}
}
order := []int{}
for len(queue) > 0 {
// Output a ready node.
node := queue[0]
queue = queue[1:]
order = append(order, node)
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
}
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
// indeg[v] = how many prerequisites v still has (incoming edges).
n := len(graph)
indeg := make([]int, n)
// Count them: every edge u -> v adds one to v's in-degree.
for _, edges := range graph {
for _, v := range edges {
indeg[v]++
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
queue := []int{}
for v := 0; v < n; v++ {
if indeg[v] == 0 {
queue = append(queue, v)
}
}
order := []int{}
for len(queue) > 0 {
// Output a ready node.
node := queue[0]
queue = queue[1:]
order = append(order, node)
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
for _, next := range graph[node] {
indeg[next]--
if indeg[next] == 0 {
queue = append(queue, next)
}
}
}
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
// indeg[v] = how many prerequisites v still has (incoming edges).
n := len(graph)
indeg := make([]int, n)
// Count them: every edge u -> v adds one to v's in-degree.
for _, edges := range graph {
for _, v := range edges {
indeg[v]++
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
queue := []int{}
for v := 0; v < n; v++ {
if indeg[v] == 0 {
queue = append(queue, v)
}
}
order := []int{}
for len(queue) > 0 {
// Output a ready node.
node := queue[0]
queue = queue[1:]
order = append(order, node)
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
for _, next := range graph[node] {
indeg[next]--
if indeg[next] == 0 {
queue = append(queue, next)
}
}
}
// If we couldn't order everything, some nodes are stuck in a cycle.
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
// indeg[v] = how many prerequisites v still has (incoming edges).
n := len(graph)
indeg := make([]int, n)
// Count them: every edge u -> v adds one to v's in-degree.
for _, edges := range graph {
for _, v := range edges {
indeg[v]++
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
queue := []int{}
for v := 0; v < n; v++ {
if indeg[v] == 0 {
queue = append(queue, v)
}
}
order := []int{}
for len(queue) > 0 {
// Output a ready node.
node := queue[0]
queue = queue[1:]
order = append(order, node)
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
for _, next := range graph[node] {
indeg[next]--
if indeg[next] == 0 {
queue = append(queue, next)
}
}
}
// If we couldn't order everything, some nodes are stuck in a cycle.
if len(order) != n {
return nil
}
return order // O(V + E)
}from collections import deque
# graph is a DAG adjacency list: an edge u -> v means u must come before v.
def topo_sort(graph):from collections import deque
# graph is a DAG adjacency list: an edge u -> v means u must come before v.
def topo_sort(graph):
# indeg[v] = how many prerequisites v still has (incoming edges).from collections import deque
# graph is a DAG adjacency list: an edge u -> v means u must come before v.
def topo_sort(graph):
# indeg[v] = how many prerequisites v still has (incoming edges).
n = len(graph)
indeg = [0] * nfrom collections import deque
# graph is a DAG adjacency list: an edge u -> v means u must come before v.
def topo_sort(graph):
# indeg[v] = how many prerequisites v still has (incoming edges).
n = len(graph)
indeg = [0] * n
# Count them: every edge u -> v adds one to v's in-degree.from collections import deque
# graph is a DAG adjacency list: an edge u -> v means u must come before v.
def topo_sort(graph):
# indeg[v] = how many prerequisites v still has (incoming edges).
n = len(graph)
indeg = [0] * n
# Count them: every edge u -> v adds one to v's in-degree.
for edges in graph:
for v in edges:
indeg[v] += 1from collections import deque
# graph is a DAG adjacency list: an edge u -> v means u must come before v.
def topo_sort(graph):
# indeg[v] = how many prerequisites v still has (incoming edges).
n = len(graph)
indeg = [0] * n
# Count them: every edge u -> v adds one to v's in-degree.
for edges in graph:
for v in edges:
indeg[v] += 1
# Nodes with no prerequisites can go first — seed the queue with them.from collections import deque
# graph is a DAG adjacency list: an edge u -> v means u must come before v.
def topo_sort(graph):
# indeg[v] = how many prerequisites v still has (incoming edges).
n = len(graph)
indeg = [0] * n
# Count them: every edge u -> v adds one to v's in-degree.
for edges in graph:
for v in edges:
indeg[v] += 1
# Nodes with no prerequisites can go first — seed the queue with them.
queue = deque()
for v in range(n):
if indeg[v] == 0:
queue.append(v)from collections import deque
# graph is a DAG adjacency list: an edge u -> v means u must come before v.
def topo_sort(graph):
# indeg[v] = how many prerequisites v still has (incoming edges).
n = len(graph)
indeg = [0] * n
# Count them: every edge u -> v adds one to v's in-degree.
for edges in graph:
for v in edges:
indeg[v] += 1
# Nodes with no prerequisites can go first — seed the queue with them.
queue = deque()
for v in range(n):
if indeg[v] == 0:
queue.append(v)
# Output a ready node.from collections import deque
# graph is a DAG adjacency list: an edge u -> v means u must come before v.
def topo_sort(graph):
# indeg[v] = how many prerequisites v still has (incoming edges).
n = len(graph)
indeg = [0] * n
# Count them: every edge u -> v adds one to v's in-degree.
for edges in graph:
for v in edges:
indeg[v] += 1
# Nodes with no prerequisites can go first — seed the queue with them.
queue = deque()
for v in range(n):
if indeg[v] == 0:
queue.append(v)
order = []
while queue:
# Output a ready node.
node = queue.popleft()
order.append(node)from collections import deque
# graph is a DAG adjacency list: an edge u -> v means u must come before v.
def topo_sort(graph):
# indeg[v] = how many prerequisites v still has (incoming edges).
n = len(graph)
indeg = [0] * n
# Count them: every edge u -> v adds one to v's in-degree.
for edges in graph:
for v in edges:
indeg[v] += 1
# Nodes with no prerequisites can go first — seed the queue with them.
queue = deque()
for v in range(n):
if indeg[v] == 0:
queue.append(v)
order = []
while queue:
# Output a ready node.
node = queue.popleft()
order.append(node)
# "Removing" it satisfies one prerequisite of each successor; any that
# hit zero are now ready themselves.from collections import deque
# graph is a DAG adjacency list: an edge u -> v means u must come before v.
def topo_sort(graph):
# indeg[v] = how many prerequisites v still has (incoming edges).
n = len(graph)
indeg = [0] * n
# Count them: every edge u -> v adds one to v's in-degree.
for edges in graph:
for v in edges:
indeg[v] += 1
# Nodes with no prerequisites can go first — seed the queue with them.
queue = deque()
for v in range(n):
if indeg[v] == 0:
queue.append(v)
order = []
while queue:
# Output a ready node.
node = queue.popleft()
order.append(node)
# "Removing" it satisfies one prerequisite of each successor; any that
# hit zero are now ready themselves.
for nxt in graph[node]:
indeg[nxt] -= 1
if indeg[nxt] == 0:
queue.append(nxt)from collections import deque
# graph is a DAG adjacency list: an edge u -> v means u must come before v.
def topo_sort(graph):
# indeg[v] = how many prerequisites v still has (incoming edges).
n = len(graph)
indeg = [0] * n
# Count them: every edge u -> v adds one to v's in-degree.
for edges in graph:
for v in edges:
indeg[v] += 1
# Nodes with no prerequisites can go first — seed the queue with them.
queue = deque()
for v in range(n):
if indeg[v] == 0:
queue.append(v)
order = []
while queue:
# Output a ready node.
node = queue.popleft()
order.append(node)
# "Removing" it satisfies one prerequisite of each successor; any that
# hit zero are now ready themselves.
for nxt in graph[node]:
indeg[nxt] -= 1
if indeg[nxt] == 0:
queue.append(nxt)
# If we couldn't order everything, some nodes are stuck in a cycle.from collections import deque
# graph is a DAG adjacency list: an edge u -> v means u must come before v.
def topo_sort(graph):
# indeg[v] = how many prerequisites v still has (incoming edges).
n = len(graph)
indeg = [0] * n
# Count them: every edge u -> v adds one to v's in-degree.
for edges in graph:
for v in edges:
indeg[v] += 1
# Nodes with no prerequisites can go first — seed the queue with them.
queue = deque()
for v in range(n):
if indeg[v] == 0:
queue.append(v)
order = []
while queue:
# Output a ready node.
node = queue.popleft()
order.append(node)
# "Removing" it satisfies one prerequisite of each successor; any that
# hit zero are now ready themselves.
for nxt in graph[node]:
indeg[nxt] -= 1
if indeg[nxt] == 0:
queue.append(nxt)
# If we couldn't order everything, some nodes are stuck in a cycle.
if len(order) != n:
return None
return order # O(V + E)// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph) {
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg = new Array(n).fill(0);
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const edges of graph) {
for (const v of edges) {
indeg[v]++;
}
}
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const edges of graph) {
for (const v of edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const edges of graph) {
for (const v of edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
const queue = [];
for (let v = 0; v < n; v++) {
if (indeg[v] === 0) {
queue.push(v);
}
}
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const edges of graph) {
for (const v of edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
const queue = [];
for (let v = 0; v < n; v++) {
if (indeg[v] === 0) {
queue.push(v);
}
}
// Output a ready node.
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const edges of graph) {
for (const v of edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
const queue = [];
for (let v = 0; v < n; v++) {
if (indeg[v] === 0) {
queue.push(v);
}
}
const order = [];
let head = 0; // a moving read index; shift() would be O(n) per pop
while (head < queue.length) {
// Output a ready node.
const node = queue[head++];
order.push(node);
}
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const edges of graph) {
for (const v of edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
const queue = [];
for (let v = 0; v < n; v++) {
if (indeg[v] === 0) {
queue.push(v);
}
}
const order = [];
let head = 0; // a moving read index; shift() would be O(n) per pop
while (head < queue.length) {
// Output a ready node.
const node = queue[head++];
order.push(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
}
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const edges of graph) {
for (const v of edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
const queue = [];
for (let v = 0; v < n; v++) {
if (indeg[v] === 0) {
queue.push(v);
}
}
const order = [];
let head = 0; // a moving read index; shift() would be O(n) per pop
while (head < queue.length) {
// Output a ready node.
const node = queue[head++];
order.push(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
for (const next of graph[node]) {
indeg[next]--;
if (indeg[next] === 0) {
queue.push(next);
}
}
}
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const edges of graph) {
for (const v of edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
const queue = [];
for (let v = 0; v < n; v++) {
if (indeg[v] === 0) {
queue.push(v);
}
}
const order = [];
let head = 0; // a moving read index; shift() would be O(n) per pop
while (head < queue.length) {
// Output a ready node.
const node = queue[head++];
order.push(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
for (const next of graph[node]) {
indeg[next]--;
if (indeg[next] === 0) {
queue.push(next);
}
}
}
// If we couldn't order everything, some nodes are stuck in a cycle.
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const edges of graph) {
for (const v of edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
const queue = [];
for (let v = 0; v < n; v++) {
if (indeg[v] === 0) {
queue.push(v);
}
}
const order = [];
let head = 0; // a moving read index; shift() would be O(n) per pop
while (head < queue.length) {
// Output a ready node.
const node = queue[head++];
order.push(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
for (const next of graph[node]) {
indeg[next]--;
if (indeg[next] === 0) {
queue.push(next);
}
}
}
// If we couldn't order everything, some nodes are stuck in a cycle.
if (order.length !== n) {
return null;
}
return order; // O(V + E)
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph: number[][]): number[] | null {
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph: number[][]): number[] | null {
// indeg[v] = how many prerequisites v still has (incoming edges).
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph: number[][]): number[] | null {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg: number[] = new Array(n).fill(0);
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph: number[][]): number[] | null {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg: number[] = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph: number[][]): number[] | null {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg: number[] = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const edges of graph) {
for (const v of edges) {
indeg[v]++;
}
}
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph: number[][]): number[] | null {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg: number[] = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const edges of graph) {
for (const v of edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph: number[][]): number[] | null {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg: number[] = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const edges of graph) {
for (const v of edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
const queue: number[] = [];
for (let v = 0; v < n; v++) {
if (indeg[v] === 0) {
queue.push(v);
}
}
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph: number[][]): number[] | null {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg: number[] = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const edges of graph) {
for (const v of edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
const queue: number[] = [];
for (let v = 0; v < n; v++) {
if (indeg[v] === 0) {
queue.push(v);
}
}
// Output a ready node.
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph: number[][]): number[] | null {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg: number[] = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const edges of graph) {
for (const v of edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
const queue: number[] = [];
for (let v = 0; v < n; v++) {
if (indeg[v] === 0) {
queue.push(v);
}
}
const order: number[] = [];
let head = 0; // a moving read index; shift() would be O(n) per pop
while (head < queue.length) {
// Output a ready node.
const node = queue[head++];
order.push(node);
}
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph: number[][]): number[] | null {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg: number[] = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const edges of graph) {
for (const v of edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
const queue: number[] = [];
for (let v = 0; v < n; v++) {
if (indeg[v] === 0) {
queue.push(v);
}
}
const order: number[] = [];
let head = 0; // a moving read index; shift() would be O(n) per pop
while (head < queue.length) {
// Output a ready node.
const node = queue[head++];
order.push(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
}
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph: number[][]): number[] | null {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg: number[] = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const edges of graph) {
for (const v of edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
const queue: number[] = [];
for (let v = 0; v < n; v++) {
if (indeg[v] === 0) {
queue.push(v);
}
}
const order: number[] = [];
let head = 0; // a moving read index; shift() would be O(n) per pop
while (head < queue.length) {
// Output a ready node.
const node = queue[head++];
order.push(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
for (const next of graph[node]) {
indeg[next]--;
if (indeg[next] === 0) {
queue.push(next);
}
}
}
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph: number[][]): number[] | null {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg: number[] = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const edges of graph) {
for (const v of edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
const queue: number[] = [];
for (let v = 0; v < n; v++) {
if (indeg[v] === 0) {
queue.push(v);
}
}
const order: number[] = [];
let head = 0; // a moving read index; shift() would be O(n) per pop
while (head < queue.length) {
// Output a ready node.
const node = queue[head++];
order.push(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
for (const next of graph[node]) {
indeg[next]--;
if (indeg[next] === 0) {
queue.push(next);
}
}
}
// If we couldn't order everything, some nodes are stuck in a cycle.
}// graph is a DAG adjacency list: an edge u -> v means u must come before v.
function topoSort(graph: number[][]): number[] | null {
// indeg[v] = how many prerequisites v still has (incoming edges).
const n = graph.length;
const indeg: number[] = new Array(n).fill(0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const edges of graph) {
for (const v of edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
const queue: number[] = [];
for (let v = 0; v < n; v++) {
if (indeg[v] === 0) {
queue.push(v);
}
}
const order: number[] = [];
let head = 0; // a moving read index; shift() would be O(n) per pop
while (head < queue.length) {
// Output a ready node.
const node = queue[head++];
order.push(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
for (const next of graph[node]) {
indeg[next]--;
if (indeg[next] === 0) {
queue.push(next);
}
}
}
// If we couldn't order everything, some nodes are stuck in a cycle.
if (order.length !== n) {
return null;
}
return order; // O(V + E)
}import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public List<Integer> topoSort(List<List<Integer>> graph) {
}
}import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public List<Integer> topoSort(List<List<Integer>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
}
}import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public List<Integer> topoSort(List<List<Integer>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.size();
int[] indeg = new int[n];
}
}import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public List<Integer> topoSort(List<List<Integer>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.size();
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
}
}import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public List<Integer> topoSort(List<List<Integer>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.size();
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
for (List<Integer> edges : graph) {
for (int v : edges) {
indeg[v]++;
}
}
}
}import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public List<Integer> topoSort(List<List<Integer>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.size();
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
for (List<Integer> edges : graph) {
for (int v : edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
}
}import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public List<Integer> topoSort(List<List<Integer>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.size();
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
for (List<Integer> edges : graph) {
for (int v : edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
Deque<Integer> queue = new ArrayDeque<>();
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue.add(v);
}
}
}
}import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public List<Integer> topoSort(List<List<Integer>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.size();
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
for (List<Integer> edges : graph) {
for (int v : edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
Deque<Integer> queue = new ArrayDeque<>();
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue.add(v);
}
}
// Output a ready node.
}
}import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public List<Integer> topoSort(List<List<Integer>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.size();
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
for (List<Integer> edges : graph) {
for (int v : edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
Deque<Integer> queue = new ArrayDeque<>();
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue.add(v);
}
}
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
// Output a ready node.
int node = queue.poll();
order.add(node);
}
}
}import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public List<Integer> topoSort(List<List<Integer>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.size();
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
for (List<Integer> edges : graph) {
for (int v : edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
Deque<Integer> queue = new ArrayDeque<>();
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue.add(v);
}
}
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
// Output a ready node.
int node = queue.poll();
order.add(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
}
}
}import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public List<Integer> topoSort(List<List<Integer>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.size();
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
for (List<Integer> edges : graph) {
for (int v : edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
Deque<Integer> queue = new ArrayDeque<>();
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue.add(v);
}
}
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
// Output a ready node.
int node = queue.poll();
order.add(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
for (int next : graph.get(node)) {
indeg[next]--;
if (indeg[next] == 0) {
queue.add(next);
}
}
}
}
}import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public List<Integer> topoSort(List<List<Integer>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.size();
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
for (List<Integer> edges : graph) {
for (int v : edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
Deque<Integer> queue = new ArrayDeque<>();
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue.add(v);
}
}
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
// Output a ready node.
int node = queue.poll();
order.add(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
for (int next : graph.get(node)) {
indeg[next]--;
if (indeg[next] == 0) {
queue.add(next);
}
}
}
// If we couldn't order everything, some nodes are stuck in a cycle.
}
}import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public List<Integer> topoSort(List<List<Integer>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.size();
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
for (List<Integer> edges : graph) {
for (int v : edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
Deque<Integer> queue = new ArrayDeque<>();
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue.add(v);
}
}
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
// Output a ready node.
int node = queue.poll();
order.add(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
for (int next : graph.get(node)) {
indeg[next]--;
if (indeg[next] == 0) {
queue.add(next);
}
}
}
// If we couldn't order everything, some nodes are stuck in a cycle.
if (order.size() != n) {
return null;
}
return order; // O(V + E)
}
}using System.Collections.Generic;
public class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public IList<int> TopoSort(IList<IList<int>> graph) {
}
}using System.Collections.Generic;
public class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public IList<int> TopoSort(IList<IList<int>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
}
}using System.Collections.Generic;
public class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public IList<int> TopoSort(IList<IList<int>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.Count;
int[] indeg = new int[n];
}
}using System.Collections.Generic;
public class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public IList<int> TopoSort(IList<IList<int>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.Count;
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
}
}using System.Collections.Generic;
public class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public IList<int> TopoSort(IList<IList<int>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.Count;
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
foreach (IList<int> edges in graph) {
foreach (int v in edges) {
indeg[v]++;
}
}
}
}using System.Collections.Generic;
public class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public IList<int> TopoSort(IList<IList<int>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.Count;
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
foreach (IList<int> edges in graph) {
foreach (int v in edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
}
}using System.Collections.Generic;
public class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public IList<int> TopoSort(IList<IList<int>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.Count;
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
foreach (IList<int> edges in graph) {
foreach (int v in edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
Queue<int> queue = new Queue<int>();
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue.Enqueue(v);
}
}
}
}using System.Collections.Generic;
public class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public IList<int> TopoSort(IList<IList<int>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.Count;
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
foreach (IList<int> edges in graph) {
foreach (int v in edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
Queue<int> queue = new Queue<int>();
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue.Enqueue(v);
}
}
// Output a ready node.
}
}using System.Collections.Generic;
public class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public IList<int> TopoSort(IList<IList<int>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.Count;
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
foreach (IList<int> edges in graph) {
foreach (int v in edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
Queue<int> queue = new Queue<int>();
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue.Enqueue(v);
}
}
List<int> order = new List<int>();
while (queue.Count > 0) {
// Output a ready node.
int node = queue.Dequeue();
order.Add(node);
}
}
}using System.Collections.Generic;
public class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public IList<int> TopoSort(IList<IList<int>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.Count;
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
foreach (IList<int> edges in graph) {
foreach (int v in edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
Queue<int> queue = new Queue<int>();
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue.Enqueue(v);
}
}
List<int> order = new List<int>();
while (queue.Count > 0) {
// Output a ready node.
int node = queue.Dequeue();
order.Add(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
}
}
}using System.Collections.Generic;
public class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public IList<int> TopoSort(IList<IList<int>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.Count;
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
foreach (IList<int> edges in graph) {
foreach (int v in edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
Queue<int> queue = new Queue<int>();
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue.Enqueue(v);
}
}
List<int> order = new List<int>();
while (queue.Count > 0) {
// Output a ready node.
int node = queue.Dequeue();
order.Add(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
foreach (int next in graph[node]) {
indeg[next]--;
if (indeg[next] == 0) {
queue.Enqueue(next);
}
}
}
}
}using System.Collections.Generic;
public class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public IList<int> TopoSort(IList<IList<int>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.Count;
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
foreach (IList<int> edges in graph) {
foreach (int v in edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
Queue<int> queue = new Queue<int>();
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue.Enqueue(v);
}
}
List<int> order = new List<int>();
while (queue.Count > 0) {
// Output a ready node.
int node = queue.Dequeue();
order.Add(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
foreach (int next in graph[node]) {
indeg[next]--;
if (indeg[next] == 0) {
queue.Enqueue(next);
}
}
}
// If we couldn't order everything, some nodes are stuck in a cycle.
}
}using System.Collections.Generic;
public class Solution {
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
public IList<int> TopoSort(IList<IList<int>> graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graph.Count;
int[] indeg = new int[n];
// Count them: every edge u -> v adds one to v's in-degree.
foreach (IList<int> edges in graph) {
foreach (int v in edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
Queue<int> queue = new Queue<int>();
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue.Enqueue(v);
}
}
List<int> order = new List<int>();
while (queue.Count > 0) {
// Output a ready node.
int node = queue.Dequeue();
order.Add(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
foreach (int next in graph[node]) {
indeg[next]--;
if (indeg[next] == 0) {
queue.Enqueue(next);
}
}
}
// If we couldn't order everything, some nodes are stuck in a cycle.
if (order.Count != n) {
return null;
}
return order; // O(V + E)
}
}#include <stdlib.h>
// graph is a DAG adjacency list: an edge u -> v means u must come before v,
// and graph[u] holds colSizes[u] successors.
int* topoSort(int** graph, int graphSize, int* colSizes, int* returnSize) {
}#include <stdlib.h>
// graph is a DAG adjacency list: an edge u -> v means u must come before v,
// and graph[u] holds colSizes[u] successors.
int* topoSort(int** graph, int graphSize, int* colSizes, int* returnSize) {
// indeg[v] = how many prerequisites v still has (incoming edges).
}#include <stdlib.h>
// graph is a DAG adjacency list: an edge u -> v means u must come before v,
// and graph[u] holds colSizes[u] successors.
int* topoSort(int** graph, int graphSize, int* colSizes, int* returnSize) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graphSize;
int* indeg = calloc(n, sizeof(int));
}#include <stdlib.h>
// graph is a DAG adjacency list: an edge u -> v means u must come before v,
// and graph[u] holds colSizes[u] successors.
int* topoSort(int** graph, int graphSize, int* colSizes, int* returnSize) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graphSize;
int* indeg = calloc(n, sizeof(int));
// Count them: every edge u -> v adds one to v's in-degree.
}#include <stdlib.h>
// graph is a DAG adjacency list: an edge u -> v means u must come before v,
// and graph[u] holds colSizes[u] successors.
int* topoSort(int** graph, int graphSize, int* colSizes, int* returnSize) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graphSize;
int* indeg = calloc(n, sizeof(int));
// Count them: every edge u -> v adds one to v's in-degree.
for (int u = 0; u < n; u++) {
for (int i = 0; i < colSizes[u]; i++) {
indeg[graph[u][i]]++;
}
}
}#include <stdlib.h>
// graph is a DAG adjacency list: an edge u -> v means u must come before v,
// and graph[u] holds colSizes[u] successors.
int* topoSort(int** graph, int graphSize, int* colSizes, int* returnSize) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graphSize;
int* indeg = calloc(n, sizeof(int));
// Count them: every edge u -> v adds one to v's in-degree.
for (int u = 0; u < n; u++) {
for (int i = 0; i < colSizes[u]; i++) {
indeg[graph[u][i]]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
}#include <stdlib.h>
// graph is a DAG adjacency list: an edge u -> v means u must come before v,
// and graph[u] holds colSizes[u] successors.
int* topoSort(int** graph, int graphSize, int* colSizes, int* returnSize) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graphSize;
int* indeg = calloc(n, sizeof(int));
// Count them: every edge u -> v adds one to v's in-degree.
for (int u = 0; u < n; u++) {
for (int i = 0; i < colSizes[u]; i++) {
indeg[graph[u][i]]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
// Each node is enqueued exactly once, so n slots is always enough.
int* queue = malloc(n * sizeof(int));
int head = 0, tail = 0;
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue[tail++] = v;
}
}
}#include <stdlib.h>
// graph is a DAG adjacency list: an edge u -> v means u must come before v,
// and graph[u] holds colSizes[u] successors.
int* topoSort(int** graph, int graphSize, int* colSizes, int* returnSize) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graphSize;
int* indeg = calloc(n, sizeof(int));
// Count them: every edge u -> v adds one to v's in-degree.
for (int u = 0; u < n; u++) {
for (int i = 0; i < colSizes[u]; i++) {
indeg[graph[u][i]]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
// Each node is enqueued exactly once, so n slots is always enough.
int* queue = malloc(n * sizeof(int));
int head = 0, tail = 0;
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue[tail++] = v;
}
}
// Output a ready node.
}#include <stdlib.h>
// graph is a DAG adjacency list: an edge u -> v means u must come before v,
// and graph[u] holds colSizes[u] successors.
int* topoSort(int** graph, int graphSize, int* colSizes, int* returnSize) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graphSize;
int* indeg = calloc(n, sizeof(int));
// Count them: every edge u -> v adds one to v's in-degree.
for (int u = 0; u < n; u++) {
for (int i = 0; i < colSizes[u]; i++) {
indeg[graph[u][i]]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
// Each node is enqueued exactly once, so n slots is always enough.
int* queue = malloc(n * sizeof(int));
int head = 0, tail = 0;
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue[tail++] = v;
}
}
int* order = malloc(n * sizeof(int));
int count = 0;
while (head < tail) {
// Output a ready node.
int node = queue[head++];
order[count++] = node;
}
}#include <stdlib.h>
// graph is a DAG adjacency list: an edge u -> v means u must come before v,
// and graph[u] holds colSizes[u] successors.
int* topoSort(int** graph, int graphSize, int* colSizes, int* returnSize) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graphSize;
int* indeg = calloc(n, sizeof(int));
// Count them: every edge u -> v adds one to v's in-degree.
for (int u = 0; u < n; u++) {
for (int i = 0; i < colSizes[u]; i++) {
indeg[graph[u][i]]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
// Each node is enqueued exactly once, so n slots is always enough.
int* queue = malloc(n * sizeof(int));
int head = 0, tail = 0;
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue[tail++] = v;
}
}
int* order = malloc(n * sizeof(int));
int count = 0;
while (head < tail) {
// Output a ready node.
int node = queue[head++];
order[count++] = node;
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
}
}#include <stdlib.h>
// graph is a DAG adjacency list: an edge u -> v means u must come before v,
// and graph[u] holds colSizes[u] successors.
int* topoSort(int** graph, int graphSize, int* colSizes, int* returnSize) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graphSize;
int* indeg = calloc(n, sizeof(int));
// Count them: every edge u -> v adds one to v's in-degree.
for (int u = 0; u < n; u++) {
for (int i = 0; i < colSizes[u]; i++) {
indeg[graph[u][i]]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
// Each node is enqueued exactly once, so n slots is always enough.
int* queue = malloc(n * sizeof(int));
int head = 0, tail = 0;
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue[tail++] = v;
}
}
int* order = malloc(n * sizeof(int));
int count = 0;
while (head < tail) {
// Output a ready node.
int node = queue[head++];
order[count++] = node;
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
for (int i = 0; i < colSizes[node]; i++) {
int next = graph[node][i];
indeg[next]--;
if (indeg[next] == 0) {
queue[tail++] = next;
}
}
}
}#include <stdlib.h>
// graph is a DAG adjacency list: an edge u -> v means u must come before v,
// and graph[u] holds colSizes[u] successors.
int* topoSort(int** graph, int graphSize, int* colSizes, int* returnSize) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graphSize;
int* indeg = calloc(n, sizeof(int));
// Count them: every edge u -> v adds one to v's in-degree.
for (int u = 0; u < n; u++) {
for (int i = 0; i < colSizes[u]; i++) {
indeg[graph[u][i]]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
// Each node is enqueued exactly once, so n slots is always enough.
int* queue = malloc(n * sizeof(int));
int head = 0, tail = 0;
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue[tail++] = v;
}
}
int* order = malloc(n * sizeof(int));
int count = 0;
while (head < tail) {
// Output a ready node.
int node = queue[head++];
order[count++] = node;
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
for (int i = 0; i < colSizes[node]; i++) {
int next = graph[node][i];
indeg[next]--;
if (indeg[next] == 0) {
queue[tail++] = next;
}
}
}
// If we couldn't order everything, some nodes are stuck in a cycle.
}#include <stdlib.h>
// graph is a DAG adjacency list: an edge u -> v means u must come before v,
// and graph[u] holds colSizes[u] successors.
int* topoSort(int** graph, int graphSize, int* colSizes, int* returnSize) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = graphSize;
int* indeg = calloc(n, sizeof(int));
// Count them: every edge u -> v adds one to v's in-degree.
for (int u = 0; u < n; u++) {
for (int i = 0; i < colSizes[u]; i++) {
indeg[graph[u][i]]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
// Each node is enqueued exactly once, so n slots is always enough.
int* queue = malloc(n * sizeof(int));
int head = 0, tail = 0;
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
queue[tail++] = v;
}
}
int* order = malloc(n * sizeof(int));
int count = 0;
while (head < tail) {
// Output a ready node.
int node = queue[head++];
order[count++] = node;
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
for (int i = 0; i < colSizes[node]; i++) {
int next = graph[node][i];
indeg[next]--;
if (indeg[next] == 0) {
queue[tail++] = next;
}
}
}
// If we couldn't order everything, some nodes are stuck in a cycle.
free(indeg);
free(queue);
if (count != n) {
free(order);
*returnSize = 0;
return NULL;
}
*returnSize = count;
return order; // caller owns the buffer. O(V + E)
}#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
vector<int> topoSort(vector<vector<int>>& graph) {
}
};#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
vector<int> topoSort(vector<vector<int>>& graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
}
};#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
vector<int> topoSort(vector<vector<int>>& graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = (int)graph.size();
vector<int> indeg(n, 0);
}
};#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
vector<int> topoSort(vector<vector<int>>& graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = (int)graph.size();
vector<int> indeg(n, 0);
// Count them: every edge u -> v adds one to v's in-degree.
}
};#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
vector<int> topoSort(vector<vector<int>>& graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = (int)graph.size();
vector<int> indeg(n, 0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const vector<int>& edges : graph) {
for (int v : edges) {
indeg[v]++;
}
}
}
};#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
vector<int> topoSort(vector<vector<int>>& graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = (int)graph.size();
vector<int> indeg(n, 0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const vector<int>& edges : graph) {
for (int v : edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
}
};#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
vector<int> topoSort(vector<vector<int>>& graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = (int)graph.size();
vector<int> indeg(n, 0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const vector<int>& edges : graph) {
for (int v : edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
queue<int> q;
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
q.push(v);
}
}
}
};#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
vector<int> topoSort(vector<vector<int>>& graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = (int)graph.size();
vector<int> indeg(n, 0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const vector<int>& edges : graph) {
for (int v : edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
queue<int> q;
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
q.push(v);
}
}
// Output a ready node.
}
};#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
vector<int> topoSort(vector<vector<int>>& graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = (int)graph.size();
vector<int> indeg(n, 0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const vector<int>& edges : graph) {
for (int v : edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
queue<int> q;
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
q.push(v);
}
}
vector<int> order;
while (!q.empty()) {
// Output a ready node.
int node = q.front();
q.pop();
order.push_back(node);
}
}
};#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
vector<int> topoSort(vector<vector<int>>& graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = (int)graph.size();
vector<int> indeg(n, 0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const vector<int>& edges : graph) {
for (int v : edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
queue<int> q;
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
q.push(v);
}
}
vector<int> order;
while (!q.empty()) {
// Output a ready node.
int node = q.front();
q.pop();
order.push_back(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
}
}
};#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
vector<int> topoSort(vector<vector<int>>& graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = (int)graph.size();
vector<int> indeg(n, 0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const vector<int>& edges : graph) {
for (int v : edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
queue<int> q;
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
q.push(v);
}
}
vector<int> order;
while (!q.empty()) {
// Output a ready node.
int node = q.front();
q.pop();
order.push_back(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
for (int next : graph[node]) {
indeg[next]--;
if (indeg[next] == 0) {
q.push(next);
}
}
}
}
};#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
vector<int> topoSort(vector<vector<int>>& graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = (int)graph.size();
vector<int> indeg(n, 0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const vector<int>& edges : graph) {
for (int v : edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
queue<int> q;
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
q.push(v);
}
}
vector<int> order;
while (!q.empty()) {
// Output a ready node.
int node = q.front();
q.pop();
order.push_back(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
for (int next : graph[node]) {
indeg[next]--;
if (indeg[next] == 0) {
q.push(next);
}
}
}
// If we couldn't order everything, some nodes are stuck in a cycle.
}
};#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
// graph is a DAG adjacency list: an edge u -> v means u must come before v.
vector<int> topoSort(vector<vector<int>>& graph) {
// indeg[v] = how many prerequisites v still has (incoming edges).
int n = (int)graph.size();
vector<int> indeg(n, 0);
// Count them: every edge u -> v adds one to v's in-degree.
for (const vector<int>& edges : graph) {
for (int v : edges) {
indeg[v]++;
}
}
// Nodes with no prerequisites can go first — seed the queue with them.
queue<int> q;
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) {
q.push(v);
}
}
vector<int> order;
while (!q.empty()) {
// Output a ready node.
int node = q.front();
q.pop();
order.push_back(node);
// "Removing" it satisfies one prerequisite of each successor; any that
// hit zero are now ready themselves.
for (int next : graph[node]) {
indeg[next]--;
if (indeg[next] == 0) {
q.push(next);
}
}
}
// If we couldn't order everything, some nodes are stuck in a cycle.
if ((int)order.size() != n) {
// An empty result means the graph had a cycle.
return {};
}
return order; // O(V + E)
}
};Tap the left half to go back, the right half to go forward.
Arrow keys or space to navigate · Esc to exit.