Topological Sort — Advanced Applications (DFS, Kahn, Cycle Detection)

from collections import deque

def topo_kahn(n, adj):
    in_deg = [0]*n
    for u in range(n):
        for v in adj[u]: in_deg[v] += 1
    q = deque(u for u in range(n) if in_deg[u]==0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0: q.append(v)
    return order if len(order)==n else []

def topo_dfs(n, adj):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE]*n
    order = []
    has_cycle = [False]

    def dfs(u):
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:
                has_cycle[0] = True
                return
            if color[v] == WHITE:
                dfs(v)
        color[u] = BLACK
        order.append(u)

    for i in range(n):
        if color[i] == WHITE:
            dfs(i)
    return [] if has_cycle[0] else order[::-1]

function topoKahn(n, adj) {
    const inDeg=new Array(n).fill(0);
    for(let u=0;u<n;u++) for(const v of adj[u]) inDeg[v]++;
    const q=[...Array(n).keys()].filter(u=>inDeg[u]===0), order=[];
    while(q.length){const u=q.shift();order.push(u);for(const v of adj[u])if(--inDeg[v]===0)q.push(v);}
    return order.length===n?order:[];
}

import java.util.*;
public int[] topoKahn(int n, List<Integer>[] adj){
    int[] inDeg=new int[n];
    for(int u=0;u<n;u++) for(int v:adj[u]) inDeg[v]++;
    Queue<Integer> q=new LinkedList<>(); for(int i=0;i<n;i++) if(inDeg[i]==0)q.offer(i);
    int[] order=new int[n]; int idx=0;
    while(!q.isEmpty()){int u=q.poll();order[idx++]=u;for(int v:adj[u])if(--inDeg[v]==0)q.offer(v);}
    return idx==n?order:new int[0];
}

#include <vector>
#include <queue>
using namespace std;
vector<int> topoKahn(int n,vector<int>adj[]){
    vector<int> inDeg(n,0);
    for(int u=0;u<n;u++) for(int v:adj[u]) inDeg[v]++;
    queue<int> q; for(int i=0;i<n;i++) if(!inDeg[i]) q.push(i);
    vector<int> order;
    while(!q.empty()){int u=q.front();q.pop();order.push_back(u);for(int v:adj[u])if(!--inDeg[v])q.push(v);}
    return order.size()==(size_t)n?order:{};
}

/* C: in-degree array + queue-based Kahn's, same as C++ above */