Basic Topological Sort Questions

bool hasCycle(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    vector<int> indeg(n, 0);
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]); indeg[e[1]]++;
    }
    queue<int> q;
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i);
    int emitted = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop(); emitted++;
        for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
    }
    return emitted < n;
}

from collections import deque
 
def has_cycle(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v); indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    emitted = 0
    while q:
        u = q.popleft(); emitted += 1
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return emitted < n

public boolean hasCycle(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    int[] indeg = new int[n];
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]); indeg[e[1]]++;
    }
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
    int emitted = 0;
    while (!q.isEmpty()) {
        int u = q.poll(); emitted++;
        for (int v : adj.get(u)) if (--indeg[v] == 0) q.offer(v);
    }
    return emitted < n;
}

from collections import deque
 
def topo_kahn(n, edges):
    adj = [[] for _ in range(n)]; indeg = [0] * n
    for u, v in edges:
        adj[u].append(v); indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    out = []
    while q:
        u = q.popleft(); out.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return out if len(out) == n else []

def topo_dfs(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges: adj[u].append(v)
    WHITE, GRAY, BLACK = 0, 1, 2
    state = [WHITE] * n
    out = []
    def dfs(u):
        state[u] = GRAY
        for v in adj[u]:
            if state[v] == GRAY: return False
            if state[v] == WHITE and not dfs(v): return False
        state[u] = BLACK
        out.append(u)
        return True
    for i in range(n):
        if state[i] == WHITE and not dfs(i): return []
    return out[::-1]

import heapq
 
def topo_lex(n, edges):
    adj = [[] for _ in range(n)]; indeg = [0] * n
    for u, v in edges:
        adj[u].append(v); indeg[v] += 1
    heap = [i for i in range(n) if indeg[i] == 0]
    heapq.heapify(heap)
    out = []
    while heap:
        u = heapq.heappop(heap); out.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0: heapq.heappush(heap, v)
    return out if len(out) == n else []

from collections import deque
 
def min_rounds(n, edges):
    adj = [[] for _ in range(n)]; indeg = [0] * n
    for u, v in edges:
        adj[u].append(v); indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    rounds = done = 0
    while q:
        rounds += 1
        for _ in range(len(q)):
            u = q.popleft(); done += 1
            for v in adj[u]:
                indeg[v] -= 1
                if indeg[v] == 0: q.append(v)
    return rounds if done == n else -1

def count_leaf_dag(n, edges):
    outdeg = [0] * n
    for u, _ in edges: outdeg[u] += 1
    return sum(1 for d in outdeg if d == 0)