Topological Sort

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
        # visit every successor of v first ...
        for k in self.graph[v]:
            if not visited[k]:
                self.topologicalSortUtil(k, visited, stack)
        # ... so v is appended only after everything that must come AFTER it (post-order)
        stack.append(v)

    def topologicalSort(self):
        visited = [False] * self.V
        stack = []
        # start a DFS from every unvisited vertex, so disconnected parts are covered
        for v in range(self.V):
            if not visited[v]:
                self.topologicalSortUtil(v, visited, stack)
        # post-order lists each node after its successors; reverse it once
        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)

# -> [0, 2, 3, 1]: every edge u -> v has u before v
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

# python
# LC 329 - Longest Increasing Path in a Matrix (memoised DFS)
# IDEA: implicit DAG (edges only go to strictly larger values) + memoised DFS
# time = O(m * n), space = O(m * n)
def longestIncreasingPath(matrix):
    m, n = len(matrix), len(matrix[0])
    memo = [[0] * n for _ in range(m)]      # 0 = not computed yet
    def dfs(i, j):
        if memo[i][j]:
            return memo[i][j]
        best = 1                            # the cell itself
        for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x, y = i + di, j + dj
            if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
                best = max(best, 1 + dfs(x, y))
        memo[i][j] = best
        return best
    return max(dfs(i, j) for i in range(m) for j in range(n))

// java
// LC 329 - Longest Increasing Path in a Matrix (memoised DFS)
// IDEA: the "move only to a bigger value" rule makes the grid a DAG, so DFS + memo computes each cell once
// time = O(m * n), space = O(m * n)
class Solution {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length, best = 0;
        int[][] memo = new int[m][n];   // 0 = not computed yet
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                best = Math.max(best, dfs(matrix, i, j, memo));
            }
        }
        return best;
    }

    private int dfs(int[][] mat, int i, int j, int[][] memo) {
        if (memo[i][j] != 0) {
            return memo[i][j];
        }
        int best = 1;
        for (int[] d : DIRS) {
            int x = i + d[0], y = j + d[1];
            if (x >= 0 && x < mat.length && y >= 0 && y < mat[0].length && mat[x][y] > mat[i][j]) {
                best = Math.max(best, 1 + dfs(mat, x, y, memo));
            }
        }
        memo[i][j] = best;
        return best;
    }
}

// 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

global scan — pseudo code
    for each edge {u, v}:                      # one pass, O(1) per edge
        if   NEXT[color[u]] == color[v]:  parent, child = u, v
        elif NEXT[color[v]] == color[u]:  parent, child = v, u
        else: return -1                        # equal colors: no direction works
        in[child]  += 1
        out[parent] += 1
    for each node x:
        if in[x] > 1 or out[x] > 2: return -1  # two parents / three children
        if in[x] == 0: root = x                # exactly one, since edges = n - 1
    return root

trace — edges = [[3,1],[3,2],[1,4],[2,0]], colors = "BRRWB"
    node color : 0=B 1=R 2=R 3=W 4=B          NEXT: R->B, B->W, W->R
    edge 3-1 : W -> R is a step   => 3 -> 1
    edge 3-2 : W -> R is a step   => 3 -> 2
    edge 1-4 : R -> B is a step   => 1 -> 4
    edge 2-0 : R -> B is a step   => 2 -> 0
    in  = [1, 1, 1, 0, 1]   out = [0, 1, 1, 2, 0]
    no in > 1, no out > 2, in == 0 only at node 3   => return 3

# python
# LC 4085 - Find Root of a Colored Tree
# IDEA: each edge's color step forces its direction -> root = the only node with no parent
def findColoredRoot(edges, colors):
    # time = O(n), space = O(n)
    n = len(colors)
    # the color a child must have, given its parent's color
    next_color = {"R": "B", "B": "W", "W": "R"}

    parent_count = [0] * n
    child_count = [0] * n

    for u, v in edges:
        if next_color[colors[u]] == colors[v]:
            parent, child = u, v
        elif next_color[colors[v]] == colors[u]:
            parent, child = v, u
        else:
            # equal colors on an edge: whichever end is the parent, the color does not advance
            return -1
        parent_count[child] += 1
        child_count[parent] += 1

    root = -1
    for node in range(n):
        if parent_count[node] > 1:      # reached from two parents -> no orientation works
            return -1
        if child_count[node] > 2:       # binary-tree property
            return -1
        if parent_count[node] == 0:
            root = node
    return root

// java
// LC 4085 - Find Root of a Colored Tree
// IDEA: each edge's color step forces its direction -> root = the only node with no parent
public class Solution {
    // time = O(n), space = O(n)
    public int findColoredRoot(int[][] edges, String colors) {
        int n = colors.length();
        int[] parentCount = new int[n];
        int[] childCount = new int[n];

        for (int[] e : edges) {
            int u = e[0], v = e[1];
            int parent, child;
            if (nextColor(colors.charAt(u)) == colors.charAt(v)) {
                parent = u;
                child = v;
            } else if (nextColor(colors.charAt(v)) == colors.charAt(u)) {
                parent = v;
                child = u;
            } else {
                return -1;   // equal colors: no direction makes the color advance
            }
            parentCount[child]++;
            childCount[parent]++;
        }

        int root = -1;
        for (int node = 0; node < n; node++) {
            if (parentCount[node] > 1) return -1;   // two parents
            if (childCount[node] > 2) return -1;    // binary-tree property
            if (parentCount[node] == 0) root = node;
        }
        return root;
    }

    // the color a child must have, given its parent's color: R -> B -> W -> R
    private char nextColor(char c) {
        if (c == 'R') return 'B';
        if (c == 'B') return 'W';
        return 'R';
    }
}

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)