Directed Acyclic Graphs (DAG)
A Directed Acyclic Graph (DAG) is a directed graph containing no cycles. If a directed graph contains a cycle, no topological ordering exists. For a valid DAG, multiple valid topological orderings may be possible.
For any vertex in a directed graph, the count of incoming edges is called in-degree, and the count of outgoing edges is called out-degree.
Topological Ordering Definition
A topological ordering of a directed graph G is a linear arrangement of its vertices such that for every directed edge (u, v), vertex u appears before vertex v in the sequence. This concept naturally models task dependencies where certain tasks must precede others.
Course Schedule II (LeetCode 210)
Model each course as a node. If course B is a prerequisite for course A, draw an edge from B to A. In any valid topological ordering, B must precede A. Computing such an ordering yields a feasible study sequence.
Depth-First Search Approach
Use a stack to record nodes that have been fully explored. For a node u, once all reachable neighbors have been completely processed, u itself becomes fully processed upon backtracking.
Three-State Marking: Each node has one of three states during traversal:
- Unvisited: The node has not been encountered yet.
- Visiting: The node is being explored but has not finished backtracking; some neighbors remain unprocessed.
- Completed: The node and all its neighbors have been fully explored and pushed onto the stack.
During each DFS round, pick any unvisited node. Mark it as Visiting, then iterate its neighbors v:
- If v is Unvisited, recursively explore v.
- If v is Visiting, a cycle is detected—no topological ordering exists.
- If v is Completed, it is already on the stack; u will be placed above v, preserving the (u, v) order.
When all neighbors of u are Completed, push u onto the stack and mark it Completed. If no cycle is found, the stack from top to bottom forms a valid topological ordering.
class Solution {
private List<List<Integer>> adjList;
private int[] nodeState; // 0=unvisited, 1=visiting, 2=completed
private int[] ordering;
private boolean cycleFound;
private int stackPtr;
public int[] findOrder(int numCourses, int[][] prerequisites) {
int total = numCourses;
adjList = new ArrayList<>();
for (int i = 0; i < total; i++) adjList.add(new ArrayList<>());
for (int[] req : prerequisites) adjList.get(req[1]).add(req[0]);
nodeState = new int[total];
ordering = new int[total];
stackPtr = total - 1;
cycleFound = false;
for (int i = 0; i < total && !cycleFound; i++) {
if (nodeState[i] == 0) traverseDFS(i);
}
if (cycleFound) return new int[0];
return ordering;
}
private void traverseDFS(int u) {
nodeState[u] = 1;
for (int neighbor : adjList.get(u)) {
if (nodeState[neighbor] == 0) traverseDFS(neighbor);
else if (nodeState[neighbor] == 1) {
cycleFound = true;
return;
}
if (cycleFound) return;
}
nodeState[u] = 2;
ordering[stackPtr--] = u;
}
}Breadth-First Search Approach (Kahn's Algorithm)
Start with nodes having zero in-degree (no prerequisites). After adding a node to the result, remove all its outgoing edges, decrementing neighbors' in-degrees. Any neighbor whose in-degree drops to zero can be processed next. Continue until all nodes are ordered or no zero-in-degree node remains (indicating a cycle).
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int total = numCourses;
int[] incomingEdges = new int[total];
List<Integer>>[] graph = new List[total];
for (int i = 0; i < total; i++) graph[i] = new ArrayList<>();
for (int[] req : prerequisites) {
int dest = req[0], src = req[1];
graph[src].add(dest);
incomingEdges[dest]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < total; i++) {
if (incomingEdges[i] == 0) queue.offer(i);
}
int[] result = new int[total];
int pos = 0;
while (!queue.isEmpty()) {
int curr = queue.poll();
result[pos++] = curr;
for (int nxt : graph[curr]) {
incomingEdges[nxt]--;
if (incomingEdges[nxt] == 0) queue.offer(nxt);
}
}
if (pos == total) return result;
return new int[0];
}
}Chain Forward Star + Array-Based Queue
class Solution {
public int[] findOrder(int totalNodes, int[][] prerequisites) {
int edgeCount = prerequisites.length;
int[] edgeHead = new int[totalNodes];
Arrays.fill(edgeHead, -1);
int[] edgeTarget = new int[edgeCount];
int[] edgeNext = new int[edgeCount];
int[] incoming = new int[totalNodes];
int eid = 0;
for (int[] pre : prerequisites) {
int dest = pre[0], src = pre[1];
edgeTarget[eid] = dest;
edgeNext[eid] = edgeHead[src];
edgeHead[src] = eid++;
incoming[dest]++;
}
int[] answer = new int[totalNodes];
int headPtr = 0;
for (int i = 0; i < totalNodes; i++) {
if (incoming[i] == 0) answer[headPtr++] = i;
}
int tailPtr = 0;
while (tailPtr < headPtr) {
int src = answer[tailPtr++];
for (int e = edgeHead[src]; e != -1; e = edgeNext[e]) {
int dest = edgeTarget[e];
if (--incoming[dest] == 0) answer[headPtr++] = dest;
}
}
if (headPtr == totalNodes) return answer;
return new int[0];
}
}Course Schedule (LeetCode 207)
DFS Cycle Detection
class Solution {
private int[] marks;
private List<Integer>>[] network;
public boolean canFinish(int numCourses, int[][] prerequisites) {
marks = new int[numCourses];
network = new List[numCourses];
for (int i = 0; i < numCourses; i++) network[i] = new ArrayList<>();
for (int[] p : prerequisites) network[p[0]].add(p[1]);
for (int i = 0; i < numCourses; i++) {
if (!explore(i)) return false;
}
return true;
}
private boolean explore(int v) {
if (marks[v] > 0) return marks[v] == 2;
marks[v] = 1;
for (int nxt : network[v]) {
if (!explore(nxt)) return false;
}
marks[v] = 2;
return true;
}
}BFS Indegree Approach
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] indeg = new int[numCourses];
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
for (int[] p : prerequisites) {
indeg[p[0]]++;
adj.get(p[1]).add(p[0]);
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.offer(i);
int count = 0;
while (!q.isEmpty()) {
int cur = q.poll();
count++;
for (int nxt : adj.get(cur)) if (--indeg[nxt] == 0) q.offer(nxt);
}
return count == numCourses;
}
}Minimum Height Trees (LeetCode 310)
Peel away leaf nodes (degree 1) layer by layer. The remaining nodes form the roots of minimum height trees.
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) return List.of(0);
List<Integer>>[] neighbors = new List[n];
int[] deg = new int[n];
for (int i = 0; i < n; i++) neighbors[i] = new ArrayList<>();
for (int[] e : edges) {
neighbors[e[0]].add(e[1]);
neighbors[e[1]].add(e[0]);
deg[e[0]]++; deg[e[1]]++;
}
List<Integer> leaves = new ArrayList<>();
for (int i = 0; i < n; i++) if (deg[i] == 1) leaves.add(i);
while (!leaves.isEmpty()) {
List<Integer> nextLeaves = new ArrayList<>();
for (int leaf : leaves) {
for (int nb : neighbors[leaf]) {
if (--deg[nb] == 1) nextLeaves.add(nb);
}
}
if (nextLeaves.isEmpty()) break;
leaves = nextLeaves;
}
return leaves;
}
}Eventual Safe States (LeetCode 802)
class Solution {
private int[][] edges;
private int[] states;
public List<Integer> eventualSafeNodes(int[][] graph) {
edges = graph;
int n = graph.length;
states = new int[n];
List<Integer> safe = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (isSafe(i)) safe.add(i);
}
return safe;
}
private boolean isSafe(int v) {
if (states[v] > 0) return states[v] == 2;
states[v] = 1;
for (int nxt : edges[v]) {
if (!isSafe(nxt)) return false;
}
states[v] = 2;
return true;
}
}Strange Printer II (LeetCode 1591)
Each color forms a rectangular region. If color b appears within color a's bounding rectangle, then a must be printed before b. Build a directed graph of color dependencies and perform topological sorting to verify feasibility.
class Solution {
public boolean isPrintable(int[][] targetGrid) {
int rows = targetGrid.length, cols = targetGrid[0].length;
int[][] bbox = new int[60][4]; // minRow, maxRow, minCol, maxCol
boolean[] hasColor = new boolean[60];
for (int i = 0; i < 60; i++) bbox[i] = new int[]{rows, 0, cols, 0};
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int c = targetGrid[i][j] - 1;
hasColor[c] = true;
bbox[c][0] = Math.min(bbox[c][0], i);
bbox[c][1] = Math.max(bbox[c][1], i);
bbox[c][2] = Math.min(bbox[c][2], j);
bbox[c][3] = Math.max(bbox[c][3], j);
}
}
boolean[][] dep = new boolean[60][60];
int[] indeg = new int[60];
for (int c = 0; c < 60; c++) {
if (!hasColor[c]) continue;
Set<Integer> seen = new HashSet<>();
for (int i = bbox[c][0]; i <= bbox[c][1]; i++) {
for (int j = bbox[c][2]; j <= bbox[c][3]; j++) {
int inner = targetGrid[i][j] - 1;
if (inner != c && !seen.contains(inner)) {
seen.add(inner);
dep[c][inner] = true;
indeg[inner]++;
}
}
}
}
Queue<Integer> q = new ArrayDeque<>();
int totalColors = 0;
for (int i = 0; i < 60; i++) {
if (!hasColor[i]) continue;
totalColors++;
if (indeg[i] == 0) q.offer(i);
}
while (!q.isEmpty()) {
int c = q.poll();
totalColors--;
for (int nxt = 0; nxt < 60; nxt++) {
if (!dep[c][nxt]) continue;
if (--indeg[nxt] == 0) q.offer(nxt);
}
}
return totalColors == 0;
}
}Construct Matrix with Conditions (LeetCode 2392)
class Solution {
public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
int[] rowPositions = computeOrder(k, rowConditions);
if (rowPositions.length == 0) return new int[0][0];
int[] colPositions = computeOrder(k, colConditions);
if (colPositions.length == 0) return new int[0][0];
int[][] matrix = new int[k][k];
for (int val = 1; val <= k; val++) {
matrix[rowPositions[val]][colPositions[val]] = val;
}
return matrix;
}
private int[] computeOrder(int k, int[][] conditions) {
List<Integer>>[] graph = new List[k + 1];
int[] indeg = new int[k + 1];
for (int i = 1; i <= k; i++) graph[i] = new ArrayList<>();
for (int[] c : conditions) {
graph[c[0]].add(c[1]);
indeg[c[1]]++;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= k; i++) if (indeg[i] == 0) q.offer(i);
int[] pos = new int[k + 1];
int idx = 0;
while (!q.isEmpty()) {
int v = q.poll();
pos[v] = idx++;
for (int nxt : graph[v]) if (--indeg[nxt] == 0) q.offer(nxt);
}
if (idx != k) return new int[0];
return pos;
}
}Topological Ordering with Answer Propagation
Dependencies define ordering. Graph construction enables traversal of dependencies. Indegree-based processing identifies starting points. Propagation transfers or updates answers along dependency chains.
Loud and Rich (LeetCode 851)
Find the quietest person among those richer than each individual. Propagate the answer from source to destination along the topological ordering.
class Solution {
public int[] loudAndRich(int[][] richer, int[] quiet) {
int n = quiet.length, m = richer.length;
int[] edgeHead = new int[n];
int[] edgeTo = new int[m];
int[] edgeNext = new int[m];
int[] indeg = new int[n];
Arrays.fill(edgeHead, -1);
int eid = 0;
for (int[] r : richer) {
int src = r[0], dest = r[1];
edgeTo[eid] = dest;
edgeNext[eid] = edgeHead[src];
edgeHead[src] = eid++;
indeg[dest]++;
}
int[] ans = new int[n];
for (int i = 0; i < n; i++) ans[i] = i;
int[] queue = new int[n];
int wr = 0, rd = 0;
for (int i = 0; i < n; i++) if (indeg[i] == 0) queue[wr++] = i;
while (rd < wr) {
int u = queue[rd++];
for (int e = edgeHead[u]; e != -1; e = edgeNext[e]) {
int v = edgeTo[e];
if (quiet[ans[u]] < quiet[ans[v]]) ans[v] = ans[u];
if (--indeg[v] == 0) queue[wr++] = v;
}
}
return ans;
}
}Iterative relaxation until stable:
class Solution {
public int[] loudAndRich(int[][] richer, int[] quiet) {
int n = quiet.length;
int[] ans = new int[n];
for (int i = 0; i < n; i++) ans[i] = i;
boolean changed = true;
while (changed) {
changed = false;
for (int[] r : richer) {
int src = r[0], dest = r[1];
if (quiet[ans[src]] < quiet[ans[dest]]) {
ans[dest] = ans[src];
changed = true;
}
}
}
return ans;
}
}Course Schedule IV (LeetCode 1462)
Determine all pairs of indirect dependencies. Use Floyd-Warshall or propagate reachability along topological ordering.
class Solution {
public List<Boolean> checkIfPrerequisite(int n, int[][] prerequisites, int[][] queries) {
boolean[][] reachable = new boolean[n][n];
for (int[] p : prerequisites) reachable[p[0]][p[1]] = true;
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
if (!reachable[i][k]) continue;
for (int j = 0; j < n; j++) {
reachable[i][j] |= reachable[k][j];
}
}
}
List<Boolean> result = new ArrayList<>();
for (int[] q : queries) result.add(reachable[q[0]][q[1]]);
return result;
}
}Find All Possible Recipes (LeetCode 2115)
class Solution {
public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
Map<String, List<String>> graph = new HashMap<>();
Map<String, Integer> need = new HashMap<>();
for (int i = 0; i < recipes.length; i++) {
String dish = recipes[i];
need.put(dish, ingredients.get(i).size());
for (String ing : ingredients.get(i)) {
graph.computeIfAbsent(ing, k -> new ArrayList<>()).add(dish);
}
}
Queue<String> q = new ArrayDeque<>();
for (String s : supplies) q.offer(s);
List<String> result = new ArrayList<>();
while (!q.isEmpty()) {
String item = q.poll();
for (String dish : graph.getOrDefault(item, new ArrayList<>())) {
int remaining = need.merge(dish, -1, Integer::sum);
if (remaining == 0) {
result.add(dish);
q.offer(dish);
}
}
}
return result;
}
}Parallel Courses III (LeetCode 2050)
class Solution {
public int minimumTime(int n, int[][] relations, int[] time) {
int m = relations.length;
int[] headArr = new int[n];
int[] nxtArr = new int[m];
int[] destArr = new int[m];
int[] indeg = new int[n];
Arrays.fill(headArr, -1);
int eid = 0;
for (int[] rel : relations) {
int u = rel[0] - 1, v = rel[1] - 1;
destArr[eid] = v;
nxtArr[eid] = headArr[u];
headArr[u] = eid++;
indeg[v]++;
}
int[] finishTime = new int[n];
for (int i = 0; i < n; i++) finishTime[i] = time[i];
int[] queue = new int[n];
int lo = 0, hi = 0;
for (int i = 0; i < n; i++) if (indeg[i] == 0) queue[hi++] = i;
while (lo < hi) {
int u = queue[lo++];
for (int e = headArr[u]; e != -1; e = nxtArr[e]) {
int v = destArr[e];
finishTime[v] = Math.max(finishTime[v], finishTime[u] + time[v]);
if (--indeg[v] == 0) queue[hi++] = v;
}
}
int maxTime = 0;
for (int t : finishTime) maxTime = Math.max(maxTime, t);
return maxTime;
}
}Ancestors in a DAG (LeetCode 2192)
class Solution {
public List<List<Integer>> getAncestors(int n, int[][] edges) {
int[] indeg = new int[n];
List<Integer>>[] graph = new List[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
for (int[] e : edges) {
graph[e[0]].add(e[1]);
indeg[e[1]]++;
}
boolean[][] ancestorMatrix = new boolean[n][n];
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : graph[u]) {
ancestorMatrix[v][u] = true;
for (int w = 0; w < n; w++) ancestorMatrix[v][w] |= ancestorMatrix[u][w];
if (--indeg[v] == 0) q.offer(v);
}
}
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < n; i++) {
List<Integer> list = new ArrayList<>();
for (int j = 0; j < n; j++) if (ancestorMatrix[i][j]) list.add(j);
result.add(list);
}
return result;
}
}Collect Coins in Tree (LeetCode 2603)
Remove coinless leaves first. Then strip two layers of remaining leaves. The surviving edges, doubled, give the minimum traversal distance (each edge must be traversed twice to return to the start).
class Solution {
public int collectTheCoins(int[] coins, int[][] edges) {
int n = coins.length;
List<Integer>>[] neighbors = new List[n];
int[] deg = new int[n];
for (int i = 0; i < n; i++) neighbors[i] = new ArrayList<>();
for (int[] e : edges) {
neighbors[e[0]].add(e[1]);
neighbors[e[1]].add(e[0]);
deg[e[0]]++; deg[e[1]]++;
}
int remainingEdges = n - 1;
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (deg[i] == 1 && coins[i] == 0) q.offer(i);
while (!q.isEmpty()) {
int u = q.poll();
deg[u]--;
if (deg[u] == 0) remainingEdges--;
for (int v : neighbors[u]) {
deg[v]--;
if (deg[v] == 1 && coins[v] == 0) q.offer(v);
}
}
for (int i = 0; i < n; i++) {
if (deg[i] == 1 && coins[i] == 1) {
deg[i]--;
remainingEdges--;
for (int v : neighbors[i]) {
deg[v]--;
if (deg[v] == 1) {
deg[v]--;
remainingEdges--;
}
}
}
}
return Math.max(0, remainingEdges * 2);
}
}Project Management (LeetCode 1203)
Perform inter-group topological sorting, then intra-group sorting within each group.
class Solution {
public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
for (int i = 0; i < n; i++) if (group[i] == -1) group[i] = m++;
List<List<Integer>> groupItems = new ArrayList<>();
for (int i = 0; i < m; i++) groupItems.add(new ArrayList<>());
for (int i = 0; i < n; i++) groupItems.get(group[i]).add(i);
List<List<Integer>> intraAdj = new ArrayList<>();
List<List<Integer>> interAdj = new ArrayList<>();
for (int i = 0; i < n; i++) intraAdj.add(new ArrayList<>());
for (int i = 0; i < m; i++) interAdj.add(new ArrayList<>());
int[] intraIndeg = new int[n];
int[] interIndeg = new int[m];
for (int i = 0; i < n; i++) {
int myGroup = group[i];
for (int pre : beforeItems.get(i)) {
if (group[pre] == myGroup) {
intraIndeg[i]++;
intraAdj.get(pre).add(i);
} else {
interIndeg[myGroup]++;
interAdj.get(group[pre]).add(myGroup);
}
}
}
List<Integer> groupOrder = topoSort(interAdj, interIndeg, createIdList(m));
if (groupOrder.isEmpty()) return new int[0];
int[] result = new int[n];
int idx = 0;
for (int gid : groupOrder) {
List<Integer> items = groupItems.get(gid);
if (items.isEmpty()) continue;
if (items.size() == 1) { result[idx++] = items.get(0); continue; }
List<Integer> sortedItems = topoSort(intraAdj, intraIndeg, items);
if (sortedItems.isEmpty()) return new int[0];
for (int item : sortedItems) result[idx++] = item;
}
return result;
}
private List<Integer> createIdList(int m) {
List<Integer> ids = new ArrayList<>();
for (int i = 0; i < m; i++) ids.add(i);
return ids;
}
private List<Integer> topoSort(List<List<Integer>> graph, int[] indeg, List<Integer> nodes) {
Queue<Integer> q = new LinkedList<>();
for (int v : nodes) if (indeg[v] == 0) q.offer(v);
List<Integer> order = new ArrayList<>();
while (!q.isEmpty()) {
int u = q.poll();
order.add(u);
for (int v : graph.get(u)) if (--indeg[v] == 0) q.offer(v);
}
return order.size() == nodes.size() ? order : new ArrayList<>();
}
}Topological Ordering with Dynamic Programming
Longest Increasing Path in Matrix (LeetCode 329)
class Solution {
private int rows, cols;
private int[][] dp, grid;
private int[] dx = {1, 0, -1, 0};
private int[] dy = {0, 1, 0, -1};
public int longestIncreasingPath(int[][] matrix) {
grid = matrix;
rows = matrix.length;
cols = matrix[0].length;
dp = new int[rows][cols];
int best = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
best = Math.max(best, computePath(i, j));
}
}
return best;
}
private int computePath(int r, int c) {
if (dp[r][c] != 0) return dp[r][c];
int maxLen = 0;
for (int d = 0; d < 4; d++) {
int nr = r + dx[d], nc = c + dy[d];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] > grid[r][c]) {
maxLen = Math.max(maxLen, computePath(nr, nc));
}
}
return dp[r][c] = 1 + maxLen;
}
}Largest Color Value in Directed Graph (LeetCode 1857)
Let dp[v][c] be the maximum count of color c across all paths ending at v. Propagate along topological ordering: dp[v][c] = max(dp[u][c]) for all predecessors u, plus 1 if v's own color equals c.
class Solution {
public int largestPathValue(String colors, int[][] edges) {
char[] colorArr = colors.toCharArray();
int nodeCount = colorArr.length, edgeCount = edges.length;
int[] headArr = new int[nodeCount];
Arrays.fill(headArr, -1);
int[] destArr = new int[edgeCount];
int[] nextArr = new int[edgeCount];
int[] indeg = new int[nodeCount];
int eid = 0;
for (int[] e : edges) {
int u = e[0], v = e[1];
destArr[eid] = v;
nextArr[eid] = headArr[u];
headArr[u] = eid++;
indeg[v]++;
}
int[] queue = new int[nodeCount];
int front = 0;
for (int i = 0; i < nodeCount; i++) if (indeg[i] == 0) queue[front++] = i;
int[][] dp = new int[nodeCount][26];
int rear = 0;
while (rear < front) {
int u = queue[rear++];
dp[u][colorArr[u] - 'a']++;
for (int e = headArr[u]; e != -1; e = nextArr[e]) {
int v = destArr[e];
for (int c = 0; c < 26; c++) {
dp[v][c] = Math.max(dp[v][c], dp[u][c]);
}
if (--indeg[v] == 0) queue[front++] = v;
}
}
if (front != nodeCount) return -1;
int maxVal = 0;
for (int[] freq : dp) for (int c : freq) maxVal = Math.max(maxVal, c);
return maxVal;
}
}Restricted Path Count (LeetCode 1786)
class Solution {
private int[] headArr, destArr, nxtArr, wtArr;
private int edgePtr;
private final int MOD = 1_000_000_007;
public int countRestrictedPaths(int n, int[][] edges) {
int totalEdges = edges.length * 2;
headArr = new int[n];
destArr = new int[totalEdges];
nxtArr = new int[totalEdges];
wtArr = new int[totalEdges];
Arrays.fill(headArr, -1);
edgePtr = 0;
for (int[] e : edges) {
int u = e[0] - 1, v = e[1] - 1, w = e[2];
addEdge(u, v, w);
addEdge(v, u, w);
}
int[] dist = new int[n];
int[] pathCnt = new int[n];
boolean[] seen = new boolean[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[n - 1] = 0;
pathCnt[n - 1] = 1;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{n - 1, 0});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int x = cur[0];
if (seen[x]) continue;
seen[x] = true;
for (int e = headArr[x]; e != -1; e = nxtArr[e]) {
int y = destArr[e];
if (dist[x] > dist[y]) pathCnt[x] = (pathCnt[x] + pathCnt[y]) % MOD;
if (dist[y] > dist[x] + wtArr[e]) {
dist[y] = dist[x] + wtArr[e];
pq.offer(new int[]{y, dist[y]});
}
}
if (x == 0) break;
}
return pathCnt[0];
}
private void addEdge(int u, int v, int w) {
destArr[edgePtr] = v;
nxtArr[edgePtr] = headArr[u];
wtArr[edgePtr] = w;
headArr[u] = edgePtr++;
}
}Longest Path with Different Adjacent Characters (LeetCode 2246)
class Solution {
public int longestPath(int[] parent, String s) {
int n = parent.length;
char[] chars = s.toCharArray();
int[] firstBest = new int[n], secondBest = new int[n], deg = new int[n];
for (int i = 1; i < n; i++) deg[parent[i]]++;
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++) if (deg[i] == 0) q.offer(i);
int maxPath = 1;
while (!q.isEmpty()) {
int node = q.poll();
int p = parent[node];
if (p == -1) break;
if (--deg[p] == 0) q.offer(p);
maxPath = Math.max(maxPath, 1 + firstBest[node] + secondBest[node]);
if (chars[node] == chars[p]) continue;
int candidate = Math.max(firstBest[node], secondBest[node]) + 1;
if (candidate > firstBest[p]) {
secondBest[p] = firstBest[p];
firstBest[p] = candidate;
} else if (candidate > secondBest[p]) {
secondBest[p] = candidate;
}
}
maxPath = Math.max(maxPath, 1 + firstBest[0] + secondBest[0]);
return maxPath;
}
}Inner-Directed Pseudotrees
Maximum Employees Invited to Meeting (LeetCode 2127)
Each node has exactly one outgoing edge, forming inner-directed pseudotrees (trees attached to cycles). Trim branches via topological sorting, then evaluate: for 2-node cycles, combine both chains; for larger cycles, take the cycle size.
class Solution {
public int maximumInvitations(int[] favorite) {
int n = favorite.length;
int[] indeg = new int[n];
for (int f : favorite) indeg[f]++;
int[] queue = new int[n];
int rd = 0, wr = 0;
for (int i = 0; i < n; i++) if (indeg[i] == 0) queue[wr++] = i;
int[] chainLen = new int[n];
while (rd < wr) {
int cur = queue[rd++];
int nxt = favorite[cur];
chainLen[nxt] = Math.max(chainLen[nxt], chainLen[cur] + 1);
if (--indeg[nxt] == 0) queue[wr++] = nxt;
}
int pairedCycles = 0, largestCycle = 0;
for (int i = 0; i < n; i++) {
if (indeg[i] == 0) continue;
int cycleSize = 1;
indeg[i] = 0;
for (int j = favorite[i]; j != i; j = favorite[j]) {
cycleSize++;
indeg[j] = 0;
}
if (cycleSize == 2) pairedCycles += 2 + chainLen[i] + chainLen[favorite[i]];
else largestCycle = Math.max(largestCycle, cycleSize);
}
return Math.max(pairedCycles, largestCycle);
}
}Union-Find Applications
Matrix Rank Transform (LeetCode 1632)
Process cells grouped by value. Within each value group, union cells sharing a row or column. Compute the maximum existing rank from the row/column for each connected component, then assign ranks and reset the union-find for the next group.
class Solution {
public int[][] matrixRankTransform(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
TreeMap<Integer, List<int[]>> valueGroups = new TreeMap<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
valueGroups.computeIfAbsent(matrix[i][j], k -> new ArrayList<>()).add(new int[]{i, j});
}
}
int[] rowPeak = new int[m], colPeak = new int[n];
int[][] result = new int[m][n];
DisjointSet ds = new DisjointSet(m + n);
int[] compRank = new int[m + n];
for (List<int[]> cells : valueGroups.values()) {
for (int[] c : cells) ds.merge(c[0], c[1] + m);
for (int[] c : cells) {
compRank[ds.root(c[0])] = Math.max(compRank[ds.root(c[0])], Math.max(rowPeak[c[0]], colPeak[c[1]]));
}
for (int[] c : cells) {
result[c[0]][c[1]] = 1 + compRank[ds.root(c[0])];
rowPeak[c[0]] = result[c[0]][c[1]];
colPeak[c[1]] = result[c[0]][c[1]];
}
for (int[] c : cells) {
ds.reset(c[0]);
ds.reset(c[1] + m);
}
}
return result;
}
}
class DisjointSet {
private int[] parent, weight;
public DisjointSet(int sz) {
parent = new int[sz];
weight = new int[sz];
for (int i = 0; i < sz; i++) { parent[i] = i; weight[i] = 1; }
}
public int root(int x) {
if (parent[x] != x) parent[x] = root(parent[x]);
return parent[x];
}
public void merge(int a, int b) {
int ra = root(a), rb = root(b);
if (ra != rb) {
if (weight[ra] > weight[rb]) { parent[rb] = ra; weight[ra] += weight[rb]; }
else { parent[ra] = rb; weight[rb] += weight[ra]; }
}
}
public void reset(int x) { parent[x] = x; weight[x] = 1; }
}Additional Problems
- Course Schedule III (LeetCode 630) — Priority queue with greedy scheduling
- Number of Increasing Paths in Grid (LeetCode 2328)
- Parallel Courses (LeetCode 1136)
- Number of Ways to Arrive at Destination (LeetCode 1976)
- Minimize Maximum Value in Grid (LeetCode 2371)
- Cat and Mouse (LeetCode 913) and Cat and Mouse II (LeetCode 1728)
- Alien Dictionary (LCR 114)
- Sequence Reconstruction (LCR 115)