Topological Sort, Dijkstra & Union-Find

import heapq
from collections import deque

def topo_order(n, edges):               # edges: (u, v) means u before v
    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); order = []
    while q:
        u = q.popleft(); order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return order if len(order) == n else []   # [] -> cycle

def dijkstra(adj, src):                 # adj[u] = [(v, w), ...]
    dist = {src: 0}; heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float('inf')): continue   # stale
        for v, w in adj[u]:
            if d + w < dist.get(v, float('inf')):
                dist[v] = d + w; heapq.heappush(heap, (d + w, v))
    return dist

class DSU:
    def __init__(self, n): self.p = list(range(n)); self.size = [1] * n
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]; x = self.p[x]
        return x
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b: return False
        if self.size[a] < self.size[b]: a, b = b, a
        self.p[b] = a; self.size[a] += self.size[b]
        return True

int[] topoOrder(int n, int[][] edges) {          // edge {u, v}: u before v
    List<List<Integer>> adj = new ArrayList<>(); int[] indeg = new int[n];
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) { adj.get(e[0]).add(e[1]); indeg[e[1]]++; }
    ArrayDeque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
    int[] order = new int[n]; int k = 0;
    while (!q.isEmpty()) { int u = q.poll(); order[k++] = u; for (int v : adj.get(u)) if (--indeg[v] == 0) q.add(v); }
    return k == n ? order : new int[0];
}

int[] dijkstra(List<List<int[]>> adj, int src) {   // adj.get(u) = {v, w}
    int[] dist = new int[adj.size()]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] = 0;
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    heap.add(new int[]{0, src});
    while (!heap.isEmpty()) {
        int[] cur = heap.poll(); int d = cur[0], u = cur[1];
        if (d > dist[u]) continue;                   // stale
        for (int[] e : adj.get(u)) if (d + e[1] < dist[e[0]]) { dist[e[0]] = d + e[1]; heap.add(new int[]{dist[e[0]], e[0]}); }
    }
    return dist;
}

class DSU {
    int[] p, size;
    DSU(int n) { p = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { p[i] = i; size[i] = 1; } }
    int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }
    boolean union(int a, int b) {
        a = find(a); b = find(b); if (a == b) return false;
        if (size[a] < size[b]) { int t = a; a = b; b = t; }
        p[b] = a; size[a] += size[b]; return true;
    }
}

vector<int> topoOrder(int n, const vector<pair<int, int>>& edges) {   // u before v
    vector<vector<int>> adj(n); vector<int> indeg(n, 0), order;
    for (auto [u, v] : edges) { adj[u].push_back(v); indeg[v]++; }
    queue<int> q; for (int i = 0; i < n; i++) if (!indeg[i]) q.push(i);
    while (!q.empty()) { int u = q.front(); q.pop(); order.push_back(u); for (int v : adj[u]) if (--indeg[v] == 0) q.push(v); }
    return (int)order.size() == n ? order : vector<int>{};
}

vector<long long> dijkstra(const vector<vector<pair<int, int>>>& adj, int src) {
    vector<long long> dist(adj.size(), LLONG_MAX); dist[src] = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> heap;
    heap.push({0, src});
    while (!heap.empty()) {
        auto [d, u] = heap.top(); heap.pop();
        if (d > dist[u]) continue;                   // stale
        for (auto [v, w] : adj[u]) if (d + w < dist[v]) { dist[v] = d + w; heap.push({dist[v], v}); }
    }
    return dist;
}

struct DSU {
    vector<int> p, sz;
    DSU(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }
    bool unite(int a, int b) {
        a = find(a); b = find(b); if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a; sz[a] += sz[b]; return true;
    }
};

function topoOrder(n, edges) {           // [u, v]: u before v
  const adj = Array.from({ length: n }, () => []), indeg = new Array(n).fill(0);
  for (const [u, v] of edges) { adj[u].push(v); indeg[v]++; }
  const order = [];
  for (let i = 0; i < n; i++) if (!indeg[i]) order.push(i);
  for (let h = 0; h < order.length; h++) for (const v of adj[order[h]]) if (--indeg[v] === 0) order.push(v);
  return order.length === n ? order : [];
}

// Dijkstra: see the MinHeap class in the Heaps lesson
function dijkstra(adj, src) {            // adj[u] = [[v, w], ...]
  const dist = new Array(adj.length).fill(Infinity), heap = new MinHeap((a, b) => a[0] < b[0]);
  dist[src] = 0; heap.push([0, src]);
  while (heap.size) {
    const [d, u] = heap.pop();
    if (d > dist[u]) continue;           // stale
    for (const [v, w] of adj[u]) if (d + w < dist[v]) { dist[v] = d + w; heap.push([dist[v], v]); }
  }
  return dist;
}

class DSU {
  constructor(n) { this.p = [...Array(n).keys()]; this.size = new Array(n).fill(1); }
  find(x) { while (this.p[x] !== x) { this.p[x] = this.p[this.p[x]]; x = this.p[x]; } return x; }
  union(a, b) {
    a = this.find(a); b = this.find(b); if (a === b) return false;
    if (this.size[a] < this.size[b]) [a, b] = [b, a];
    this.p[b] = a; this.size[a] += this.size[b]; return true;
  }
}