拓撲排序 - 完整指南

def topologicalSort_BFS(numNodes, edges):
    """
    BFS-based topological sort using in-degree tracking.
    Time: O(V + E), Space: O(V)
    """
    from collections import defaultdict, deque
    
    # Build graph and calculate in-degrees
    graph = defaultdict(list)
    in_degree = [0] * numNodes
    
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    # Initialize queue with nodes having no dependencies
    queue = deque([i for i in range(numNodes) if in_degree[i] == 0])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        # Process neighbors
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # Check for cycles
    return result if len(result) == numNodes else []

// Java version
public List<Integer> topologicalSort_BFS(int numNodes, int[][] edges) {
    Map<Integer, List<Integer>> graph = new HashMap<>();
    int[] inDegree = new int[numNodes];
    
    // Build graph
    for (int i = 0; i < numNodes; i++) {
        graph.put(i, new ArrayList<>());
    }
    
    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        inDegree[edge[1]]++;
    }
    
    // BFS
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numNodes; i++) {
        if (inDegree[i] == 0) queue.offer(i);
    }
    
    List<Integer> result = new ArrayList<>();
    while (!queue.isEmpty()) {
        int node = queue.poll();
        result.add(node);
        
        for (int neighbor : graph.get(node)) {
            if (--inDegree[neighbor] == 0) {
                queue.offer(neighbor);
            }
        }
    }
    
    return result.size() == numNodes ? result : new ArrayList<>();
}

def topologicalSort_DFS(numNodes, edges):
    """
    DFS-based topological sort with three-color marking.
    Time: O(V + E), Space: O(V)
    """
    from collections import defaultdict
    
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
    
    # 0: white (unvisited), 1: gray (visiting), 2: black (visited)
    color = [0] * numNodes
    result = []
    has_cycle = False
    
    def dfs(node):
        nonlocal has_cycle
        if color[node] == 1:  # Gray = cycle detected
            has_cycle = True
            return
        if color[node] == 2:  # Black = already processed
            return
        
        color[node] = 1  # Mark as visiting
        for neighbor in graph[node]:
            dfs(neighbor)
        color[node] = 2  # Mark as visited
        result.append(node)  # Add to result in reverse order
    
    for i in range(numNodes):
        if color[i] == 0:
            dfs(i)
    
    return [] if has_cycle else result[::-1]

// Java version
public List<Integer> topologicalSort_DFS(int numNodes, int[][] edges) {
    Map<Integer, List<Integer>> graph = new HashMap<>();
    for (int i = 0; i < numNodes; i++) {
        graph.put(i, new ArrayList<>());
    }
    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
    }
    
    int[] color = new int[numNodes]; // 0: white, 1: gray, 2: black
    List<Integer> result = new ArrayList<>();
    boolean[] hasCycle = {false};
    
    for (int i = 0; i < numNodes; i++) {
        if (color[i] == 0) {
            dfs(i, graph, color, result, hasCycle);
        }
    }
    
    if (hasCycle[0]) return new ArrayList<>();
    Collections.reverse(result);
    return result;
}

private void dfs(int node, Map<Integer, List<Integer>> graph, 
                 int[] color, List<Integer> result, boolean[] hasCycle) {
    if (color[node] == 1) {
        hasCycle[0] = true;
        return;
    }
    if (color[node] == 2) return;
    
    color[node] = 1;
    for (int neighbor : graph.get(node)) {
        dfs(neighbor, graph, color, result, hasCycle);
    }
    color[node] = 2;
    result.add(node);
}

# V0
# IDEA : implement topologicalSortUtil, topologicalSort, and addEdge methods
# step 1) maintain a stack, save "ordering" nodes in it (and return in final step)
# step 2) init visited as [False]*self.V  (all nodes are NOT visited yet)
# step 3) iterate over all vertices in graph, if not visited, then run topologicalSortUtil
# step 4) return result (stack)
from collections import defaultdict
class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices

    # for build graph
    def addEdge(self, u, v):
        self.graph[u].append(v)

    def topologicalSortUtil(self, v, visited, stack):
        visited[v] = True

        ### NOTE this !!! (self.graph[v])
        for k in self.graph[v]:
            if visited[k] == False:
                self.topologicalSortUtil(k, visited, stack)
        # stack.insert(0,v) # instead of insert v to idx = 0, we can still append v to stack and reverse it and return (e.g. return stack[::-1])
        """
        ### NOTE !! stack.append(v) is wrong, we SHOULD use  stack.insert(0,v)
        """
        stack.insert(0,v)

    def topologicalSort(self):
        visited = [False] * self.V
        stack = []
        ### NOTE this !!! (range(self.V))
        for v in range(self.V):
            # call tologicalSortUtil only if visited[v] == False (the vertice is not visited yet)
            if visited[v] == False:
                self.topologicalSortUtil(v, visited, stack)
        # return the result in inverse order
        return stack[::-1]

### TEST
{"A": 0, "B":1, "C":2, "D": 3}
v = 4
g = Graph(v)
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(2, 3)
g.addEdge(3, 1)

print (g.graph)

# ans should be TableB, TableD, TableC, TableA.
r = g.topologicalSort()
print (r)

def topologicalSort_Lexicographical(numNodes, edges):
    """
    Find smallest lexicographical topological order.
    Time: O((V + E) log V), Space: O(V)
    """
    from collections import defaultdict
    import heapq
    
    graph = defaultdict(list)
    in_degree = [0] * numNodes
    
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    # Use min-heap for smallest lexicographical order
    heap = [i for i in range(numNodes) if in_degree[i] == 0]
    heapq.heapify(heap)
    result = []
    
    while heap:
        node = heapq.heappop(heap)
        result.append(node)
        
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                heapq.heappush(heap, neighbor)
    
    return result if len(result) == numNodes else []

// Java version
public List<Integer> topologicalSort_Lexicographical(int numNodes, int[][] edges) {
    Map<Integer, List<Integer>> graph = new HashMap<>();
    int[] inDegree = new int[numNodes];
    
    for (int i = 0; i < numNodes; i++) {
        graph.put(i, new ArrayList<>());
    }
    
    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        inDegree[edge[1]]++;
    }
    
    // Min-heap for lexicographical order
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int i = 0; i < numNodes; i++) {
        if (inDegree[i] == 0) pq.offer(i);
    }
    
    List<Integer> result = new ArrayList<>();
    while (!pq.isEmpty()) {
        int node = pq.poll();
        result.add(node);
        
        for (int neighbor : graph.get(node)) {
            if (--inDegree[neighbor] == 0) {
                pq.offer(neighbor);
            }
        }
    }
    
    return result.size() == numNodes ? result : new ArrayList<>();
}

def allTopologicalSorts(graph, in_degree, path, result, visited):
    """
    Find all possible topological orderings.
    Time: O(V! × (V + E)), Space: O(V)
    """
    if len(path) == len(graph):
        result.append(path[:])
        return
    
    for node in range(len(graph)):
        if in_degree[node] == 0 and not visited[node]:
            # Choose node
            visited[node] = True
            path.append(node)
            
            # Update in-degrees
            for neighbor in graph[node]:
                in_degree[neighbor] -= 1
            
            # Recurse
            allTopologicalSorts(graph, in_degree, path, result, visited)
            
            # Backtrack
            for neighbor in graph[node]:
                in_degree[neighbor] += 1
            path.pop()
            visited[node] = False

# Usage
def findAllOrders(numNodes, edges):
    from collections import defaultdict
    
    graph = defaultdict(list)
    in_degree = [0] * numNodes
    
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    result = []
    visited = [False] * numNodes
    allTopologicalSorts(graph, in_degree, [], result, visited)
    return result

def parallelTaskScheduling(numTasks, edges, times):
    """
    Find minimum time to complete all tasks with parallel execution.
    Time: O(V + E), Space: O(V)
    """
    from collections import defaultdict, deque
    
    graph = defaultdict(list)
    in_degree = [0] * numTasks
    
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    # Track completion time for each task
    completion_time = [0] * numTasks
    queue = deque()
    
    # Initialize with tasks having no dependencies
    for i in range(numTasks):
        if in_degree[i] == 0:
            queue.append(i)
            completion_time[i] = times[i]
    
    while queue:
        task = queue.popleft()
        
        for next_task in graph[task]:
            # Update completion time
            completion_time[next_task] = max(
                completion_time[next_task],
                completion_time[task] + times[next_task]
            )
            
            in_degree[next_task] -= 1
            if in_degree[next_task] == 0:
                queue.append(next_task)
    
    return max(completion_time)

// Java version
public int parallelTaskScheduling(int numTasks, int[][] edges, int[] times) {
    Map<Integer, List<Integer>> graph = new HashMap<>();
    int[] inDegree = new int[numTasks];
    int[] completionTime = new int[numTasks];
    
    for (int i = 0; i < numTasks; i++) {
        graph.put(i, new ArrayList<>());
    }
    
    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        inDegree[edge[1]]++;
    }
    
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numTasks; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
            completionTime[i] = times[i];
        }
    }
    
    while (!queue.isEmpty()) {
        int task = queue.poll();
        
        for (int nextTask : graph.get(task)) {
            completionTime[nextTask] = Math.max(
                completionTime[nextTask],
                completionTime[task] + times[nextTask]
            );
            
            if (--inDegree[nextTask] == 0) {
                queue.offer(nextTask);
            }
        }
    }
    
    int maxTime = 0;
    for (int time : completionTime) {
        maxTime = Math.max(maxTime, time);
    }
    return maxTime;
}

        0                 layer 1 leaves: 2, 3, 5        remaining = 6 - 3 = 3
        |                 remove them
        1              ────────────────────────────────
      / | \                 0 - 1 - 4
     2  3  4             layer 2 leaves: 0, 4            remaining = 3 - 2 = 1
           |             remove them
           5           ────────────────────────────────
                              1                          remaining = 1 → stop, answer [1]

even node count on the diameter          odd node count on the diameter
A - B - C - D                            A - B - C - D - E
    ↑   ↑                                        ↑
  two centers → [B, C]                      one center → [C]

def findMinHeightTrees(n, edges):
    """
    Find tree centroids by trimming leaves layer by layer.
    Time: O(V + E), Space: O(V)
    """
    from collections import deque

    # Edge case: single node
    if n == 1:
        return [0]

    # Build adjacency list and track degrees
    graph = [[] for _ in range(n)]
    degree = [0] * n

    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
        degree[u] += 1
        degree[v] += 1

    # Initialize queue with all leaf nodes (degree = 1)
    leaves = deque([i for i in range(n) if degree[i] == 1])

    # Trim leaves layer by layer
    remaining = n
    while remaining > 2:
        leaf_count = len(leaves)
        remaining -= leaf_count

        for _ in range(leaf_count):
            leaf = leaves.popleft()

            # Process neighbors of current leaf
            for neighbor in graph[leaf]:
                degree[neighbor] -= 1
                # If neighbor becomes a leaf, add to queue
                if degree[neighbor] == 1:
                    leaves.append(neighbor)

    # The remaining nodes (1 or 2) are the centroids
    return list(leaves)

// Java version
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    // Edge case: single node
    if (n == 1) {
        return Collections.singletonList(0);
    }

    // Build adjacency list and track degrees
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }

    int[] degree = new int[n];

    for (int[] edge : edges) {
        int u = edge[0], v = edge[1];
        graph.get(u).add(v);
        graph.get(v).add(u);
        degree[u]++;
        degree[v]++;
    }

    // Initialize queue with all leaf nodes (degree = 1)
    Queue<Integer> leaves = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (degree[i] == 1) {
            leaves.offer(i);
        }
    }

    // Trim leaves layer by layer
    int remaining = n;
    while (remaining > 2) {
        int leafCount = leaves.size();
        remaining -= leafCount;

        for (int i = 0; i < leafCount; i++) {
            int leaf = leaves.poll();

            // Process neighbors of current leaf
            for (int neighbor : graph.get(leaf)) {
                degree[neighbor]--;
                // If neighbor becomes a leaf, add to queue
                if (degree[neighbor] == 1) {
                    leaves.offer(neighbor);
                }
            }
        }
    }

    // The remaining nodes (1 or 2) are the centroids
    return new ArrayList<>(leaves);
}

class UnionFind:
    """
    Union Find with path compression and union by rank.
    Time: O(α(N)) per operation (nearly O(1)), Space: O(N)
    """
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # number of connected components

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        # union by rank
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.count -= 1

// Java version
class UnionFind {
    int[] parent;
    int[] rank;
    int count;

    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // path compression
        }
        return parent[x];
    }

    void union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;
        // union by rank
        if (rank[px] < rank[py]) {
            parent[px] = py;
        } else if (rank[px] > rank[py]) {
            parent[py] = px;
        } else {
            parent[py] = px;
            rank[px]++;
        }
        count--;
    }
}

// java
// LC 329 - Longest Increasing Path in a Matrix
// IDEA: implicit DAG (cell -> strictly larger neighbour) + Kahn's peeling from sinks;
//       answer = number of peeling layers = longest path length
public class Solution {
    // time = O(m * n), space = O(m * n)
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;

        // step 1) out-degree = how many strictly-larger neighbours a cell points to
        int[][] outdeg = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int[] d : DIRS) {
                    int x = i + d[0], y = j + d[1];
                    if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                        outdeg[i][j]++;
                    }
                }
            }
        }

        // step 2) seed the queue with the sinks (local maxima)
        Deque<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (outdeg[i][j] == 0) q.offer(new int[]{i, j});
            }
        }

        // step 3) peel layer by layer; each layer = +1 on the longest path
        int length = 0;
        while (!q.isEmpty()) {
            length++;
            for (int sz = q.size(); sz > 0; sz--) {
                int[] cur = q.poll();
                int i = cur[0], j = cur[1];
                for (int[] d : DIRS) {
                    int x = i + d[0], y = j + d[1];
                    // walk backwards along the implicit edge (smaller neighbour)
                    if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] < matrix[i][j]) {
                        if (--outdeg[x][y] == 0) q.offer(new int[]{x, y});
                    }
                }
            }
        }
        return length;
    }
}

# python
# LC 329 - Longest Increasing Path in a Matrix
# IDEA: implicit DAG (cell -> strictly larger neighbour) + Kahn's peeling from sinks
from collections import deque

def longestIncreasingPath(matrix):
    # time = O(m * n), space = O(m * n)
    if not matrix or not matrix[0]:
        return 0

    m, n = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))

    # step 1) out-degree = number of strictly-larger neighbours
    outdeg = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            for di, dj in dirs:
                x, y = i + di, j + dj
                if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
                    outdeg[i][j] += 1

    # step 2) seed with sinks (local maxima)
    q = deque((i, j) for i in range(m) for j in range(n) if outdeg[i][j] == 0)

    # step 3) peel; layer count == longest increasing path
    length = 0
    while q:
        length += 1
        for _ in range(len(q)):
            i, j = q.popleft()
            for di, dj in dirs:
                x, y = i + di, j + dj
                if 0 <= x < m and 0 <= y < n and matrix[x][y] < matrix[i][j]:
                    outdeg[x][y] -= 1
                    if outdeg[x][y] == 0:
                        q.append((x, y))
    return length

// java
// LC 1557 - Minimum Number of Vertices to Reach All Nodes
// IDEA: on a DAG, the minimal start set == exactly the nodes with in-degree 0
public class Solution {
    // time = O(V + E), space = O(V)
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        boolean[] hasIncoming = new boolean[n];
        for (List<Integer> e : edges) {
            hasIncoming[e.get(1)] = true;
        }

        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!hasIncoming[i]) res.add(i);
        }
        return res;
    }
}

# python
# LC 1557 - Minimum Number of Vertices to Reach All Nodes
# IDEA: on a DAG, the minimal start set == exactly the nodes with in-degree 0
def findSmallestSetOfVertices(n, edges):
    # time = O(V + E), space = O(V)
    has_incoming = [False] * n
    for _, v in edges:
        has_incoming[v] = True
    return [i for i in range(n) if not has_incoming[i]]

# python
# LC 997 - Find the Town Judge
# IDEA: judge == trusted by everyone else (in = n-1) and trusts nobody (out = 0)
def findJudge(n, trust):
    # time = O(V + E), space = O(V)
    # labels are 1..n, so size n + 1 and ignore index 0
    in_degree = [0] * (n + 1)
    out_degree = [0] * (n + 1)

    for a, b in trust:          # a trusts b
        out_degree[a] += 1
        in_degree[b] += 1

    for person in range(1, n + 1):
        if out_degree[person] == 0 and in_degree[person] == n - 1:
            return person
    return -1

// java
// LC 997 - Find the Town Judge
// IDEA: judge == in-degree (n-1) and out-degree 0  =>  score = in - out == n - 1
public class Solution {
    // time = O(V + E), space = O(V)
    public int findJudge(int n, int[][] trust) {
        int[] score = new int[n + 1];
        for (int[] t : trust) {
            score[t[0]]--;   // t[0] trusts someone -> out-degree
            score[t[1]]++;   // t[1] is trusted     -> in-degree
        }
        for (int i = 1; i <= n; i++) {
            if (score[i] == n - 1) return i;
        }
        return -1;
    }
}

# python
# LC 997 - Find the Town Judge
def findJudge(n, trust):
    # time = O(V + E), space = O(V)
    score = [0] * (n + 1)
    for a, b in trust:
        score[a] -= 1   # a trusts someone -> out-degree
        score[b] += 1   # b is trusted     -> in-degree
    for i in range(1, n + 1):
        if score[i] == n - 1:
            return i
    return -1

// java
// LC 1361 - Validate Binary Tree Nodes
// IDEA: in-degree <= 1 for all + exactly one in-degree-0 root + root reaches all n nodes
public class Solution {
    // time = O(N), space = O(N)
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        // (1) no node may have two parents
        int[] indeg = new int[n];
        for (int i = 0; i < n; i++) {
            for (int c : new int[]{leftChild[i], rightChild[i]}) {
                if (c != -1 && ++indeg[c] > 1) return false;
            }
        }

        // (2) exactly one root
        int root = -1;
        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) {
                if (root != -1) return false;   // 2+ roots => forest
                root = i;
            }
        }
        if (root == -1) return false;           // 0 roots => everything is in a cycle

        // (3) the root must reach every node (else a detached cycle exists)
        int seen = 1;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            int node = stack.pop();
            for (int c : new int[]{leftChild[node], rightChild[node]}) {
                if (c != -1) {
                    seen++;
                    stack.push(c);
                }
            }
        }
        return seen == n;
    }
}

# python
# LC 1361 - Validate Binary Tree Nodes
def validateBinaryTreeNodes(n, leftChild, rightChild):
    # time = O(N), space = O(N)
    # (1) no node may have two parents
    indeg = [0] * n
    for i in range(n):
        for c in (leftChild[i], rightChild[i]):
            if c != -1:
                indeg[c] += 1
                if indeg[c] > 1:
                    return False

    # (2) exactly one root
    roots = [i for i in range(n) if indeg[i] == 0]
    if len(roots) != 1:
        return False

    # (3) root must reach every node
    seen, stack = 1, [roots[0]]
    while stack:
        node = stack.pop()
        for c in (leftChild[node], rightChild[node]):
            if c != -1:
                seen += 1
                stack.append(c)
    return seen == n

START: Topological Sort Problem
│
├── Working with undirected tree?
│   │
│   ├── YES → Finding tree center/centroid?
│   │   │
│   │   ├── YES → Use Template 7 (Tree Centroid Finding)
│   │   │
│   │   └── NO → Continue
│   │
│   └── NO → Continue
│
├── Need all valid orderings?
│   │
│   ├── YES → Use Template 5 (Backtracking)
│   │
│   └── NO → Continue
│
├── Need lexicographical order?
│   │
│   ├── YES → Use Template 4 (Priority Queue)
│   │
│   └── NO → Continue
│
├── Need parallel execution time?
│   │
│   ├── YES → Use Template 6 (Level BFS)
│   │
│   └── NO → Continue
│
├── Need to count connected components?
│   │
│   ├── YES → Use Template 8 (Union Find)
│   │
│   └── NO → Continue
│
├── Need cycle detection only?
│   │
│   ├── YES → Use Template 2 (Three-Color DFS)
│   │
│   └── NO → Continue
│
└── DEFAULT → Use Template 1 (BFS Kahn's Algorithm)