Topological Sort and Union-Find

Topological Sort

Applicable only to Directed Acyclic Graphs (DAGs), topological sorting provides a linear ordering of tasks based on their dependencies.

BFS Approach (Kahn's Algorithm - Recommended)

int[] topoSort(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<>();
    int[] inDegree = new int[n];
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    
    // 1. Build adjacency list and calculate in-degrees
    for (int[] e : edges) {
        graph.get(e[0]).add(e[1]);
        inDegree[e[1]]++;
    }
    
    // 2. Queue all nodes with no dependencies
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) if (inDegree[i] == 0) queue.offer(i);
    
    int[] order = new int[n];
    int idx = 0;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        order[idx++] = u;
        for (int v : graph.get(u)) {
            // Once a dependency is met, decrement in-degree
            if (--inDegree[v] == 0) queue.offer(v);
        }
    }
    
    // 3. Cycle Detection: if we didn't visit all nodes, a cycle must exist
    return idx == n ? order : new int[]{};
}

DFS Approach (Post-order Reversal)

Processes nodes and adds them to a result list only after all their children are visited. Reversing this list yields the topological order.

int[] color; // 0=Unvisited, 1=Visiting, 2=Visited
List<Integer> resultList;
boolean isCyclic = false;

boolean dfs(int u, List<List<Integer>> adj) {
    color[u] = 1; // Mark as Gray (Processing)
    for (int v : adj.get(u)) {
        if (color[v] == 1) { isCyclic = true; return false; }
        if (color[v] == 0 && !dfs(v, adj)) return false;
    }
    color[u] = 2; // Mark as Black (Finished)
    resultList.add(u); // Add to post-order list
    return true;
}

Union-Find (DSU)

An efficient structure for managing Disjoint Sets and checking connectivity.

class UnionFind {
    private final int[] parent;
    private final int[] rank;

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

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

    // Union by Rank
    boolean union(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return false;
        
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }

    boolean connected(int x, int y) { return find(x) == find(y); }
}

Practical Applications

Redundant Connection (LeetCode 684)

An edge is redundant in a tree if adding it joins two nodes that are already part of the same connected component (forming a cycle).

int[] findRedundantConnection(int[][] edges) {
    UnionFind uf = new UnionFind(edges.length + 1);
    for (int[] e : edges) {
        if (!uf.union(e[0], e[1])) return e;
    }
    return new int[]{};
}

Minimum Spanning Tree (Kruskal's Algorithm)

Combining DSU with Greedy: Add the cheapest possible edge that doesn't create a cycle until all nodes are connected.

int minCostConnectPoints(int[][] points) {
    int n = points.length;
    List<int[]> edges = new ArrayList<>();
    
    // Generate all potential edges (Manhattan distance)
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int dist = Math.abs(points[i][0]-points[j][0]) + Math.abs(points[i][1]-points[j][1]);
            edges.add(new int[]{dist, i, j});
        }
    }
    
    // Sort edges by weight
    edges.sort(Comparator.comparingInt(e -> e[0]));
    
    UnionFind uf = new UnionFind(n);
    int totalCost = 0, edgesUsed = 0;
    
    for (int[] e : edges) {
        if (uf.union(e[1], e[2])) {
            totalCost += e[0];
            if (++edgesUsed == n - 1) break;
        }
    }
    return totalCost;
}