Advanced Graphs

class UnionFind {
    private int[] parent;  // parent[i] = parent of element i
    private int[] rank;    // rank[i] = approximate height of subtree
    private int count;     // Number of connected components
    
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;  // Initially n separate components
        
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // Each element is its own parent
            rank[i] = 0;    // Initial rank is 0
        }
    }
}

Creates n separate sets where each element points to itself. Think of it as n separate friend groups of size 1. The rank array helps keep trees balanced during union operations.

    // Find with path compression - O(α(n)) ≈ O(1)
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // Path compression magic!
        }
        return parent[x];
    }

Finds the root (representative) of x's set. The magic is path compression: while finding root, we make every node on the path point directly to root. Future finds for these nodes become O(1)!

    // Union by rank - keeps trees balanced
    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX == rootY) return false;  // Already in same set
        
        // Attach smaller tree under larger tree
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;  // Increase rank only when equal
        }
        
        count--;  // One less component
        return true;
    }

Merges two sets by attaching smaller tree under larger one. This keeps tree height minimal (logarithmic). Returns false if already connected - useful for cycle detection! Decrements component count on successful merge.

    // Check if x and y are in the same set
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
    
    // Get number of connected components
    public int getCount() {
        return count;
    }
}

Helper methods for common queries. connected() checks if two elements belong to same set by comparing their roots. getCount() returns how many separate groups exist - starts at n and decreases with each union.

// Number of Connected Components in Graph
int countComponents(int n, int[][] edges) {
    UnionFind uf = new UnionFind(n);
    
    for (int[] edge : edges) {
        uf.union(edge[0], edge[1]);  // Connect endpoints
    }
    
    return uf.getCount();  // Remaining separate components
}

Classic application: count how many "islands" or separate groups exist after processing all edges. Start with n components, each successful union reduces count by 1. Final count = number of disconnected groups.

// Detect Cycle in Undirected Graph
boolean hasCycle(int n, int[][] edges) {
    UnionFind uf = new UnionFind(n);
    
    for (int[] edge : edges) {
        // If already connected, adding edge creates cycle!
        if (!uf.union(edge[0], edge[1])) {
            return true;  // Cycle found
        }
    }
    
    return false;  // No cycle
}

Elegant cycle detection! If two nodes are already in the same set (union returns false), adding an edge between them creates a cycle. This is exactly how Kruskal's MST algorithm avoids cycles when adding edges.

// Kruskal's Algorithm - O(E log E)
int kruskalMST(int n, int[][] edges) {
    // Sort edges by weight (greedy approach)
    Arrays.sort(edges, (a, b) -> a[2] - b[2]);
    
    UnionFind uf = new UnionFind(n);
    int mstWeight = 0;
    int edgesUsed = 0;
}

Sort all edges from smallest to largest weight - this is the greedy foundation. Initialize Union-Find to track connected components and detect cycles. We'll greedily pick smallest edges that don't create cycles.

    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], weight = edge[2];
        
        // Add edge only if it doesn't create a cycle
        if (uf.union(u, v)) {
            mstWeight += weight;
            edgesUsed++;
            
            if (edgesUsed == n - 1) break;  // MST complete!
        }
    }

For each edge (in sorted order), try to add it. Union-Find's union() returns true only if endpoints are in different components - meaning no cycle! Stop when we have V-1 edges (minimum needed to connect V vertices).

    // Return MST weight, or -1 if graph is disconnected
    return edgesUsed == n - 1 ? mstWeight : -1;
}

If we couldn't add V-1 edges, the graph is disconnected (no MST exists). Otherwise return total weight of all edges in MST. This handles edge case of disconnected input graphs.

// Variant: Get actual MST edges (not just total weight)
List getMSTEdges(int n, int[][] edges) {
    Arrays.sort(edges, (a, b) -> a[2] - b[2]);
    
    UnionFind uf = new UnionFind(n);
    List mst = new ArrayList<>();
    
    for (int[] edge : edges) {
        if (uf.union(edge[0], edge[1])) {
            mst.add(edge);  // Store the actual edge
            if (mst.size() == n - 1) break;
        }
    }
    
    return mst;  // List of edges in MST
}

Sometimes you need the actual edges, not just total weight. This variant stores each selected edge in a list. Useful when you need to know which connections to build (e.g., which cables to lay between cities).

// Prim's Algorithm - O((V + E) log V)
int primMST(int n, List> adj) {
    boolean[] inMST = new boolean[n];  // Track vertices in MST
    // Min-heap: {weight, vertex}
    PriorityQueue pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    
    pq.offer(new int[]{0, 0});  // Start from vertex 0 with weight 0
    int mstWeight = 0;
    int edgesUsed = 0;
}

Initialize a min-heap (priority queue) sorted by edge weight. Start from any vertex (here vertex 0) with weight 0. The inMST array prevents adding the same vertex twice, which would create a cycle.

    while (!pq.isEmpty() && edgesUsed < n) {
        int[] curr = pq.poll();  // Get minimum weight edge
        int weight = curr[0], u = curr[1];
        
        if (inMST[u]) continue;  // Skip if already in MST
        
        inMST[u] = true;      // Add vertex to MST
        mstWeight += weight;   // Add edge weight to total
        edgesUsed++;
    }

Extract the minimum weight edge from heap. If the vertex is already in MST, skip it (we found a cheaper path earlier). Otherwise, add vertex to MST and accumulate weight. This greedy choice guarantees minimum total weight.

        // Add all edges to non-MST neighbors
        for (int[] edge : adj.get(u)) {
            int v = edge[0], w = edge[1];
            if (!inMST[v]) {
                pq.offer(new int[]{w, v});  // Add to heap
            }
        }
    }
    
    return edgesUsed == n ? mstWeight : -1;  // -1 if disconnected
}

For the newly added vertex, push all its edges to non-MST vertices into the heap. The heap automatically sorts them, so next iteration picks the globally cheapest edge connecting MST to a new vertex. Return -1 if graph is disconnected.

// LeetCode: Min Cost to Connect All Points (Manhattan Distance)
int minCostConnectPoints(int[][] points) {
    int n = points.length;
    boolean[] inMST = new boolean[n];
    PriorityQueue pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    
    pq.offer(new int[]{0, 0});  // Start from point 0
    int cost = 0;
    int count = 0;
    
    while (count < n) {
        int[] curr = pq.poll();
        int d = curr[0], u = curr[1];
        
        if (inMST[u]) continue;
        inMST[u] = true;
        cost += d;
        count++;
        
        // Add edges to ALL other points (complete graph)
        for (int v = 0; v < n; v++) {
            if (!inMST[v]) {
                int dist = Math.abs(points[u][0] - points[v][0]) + 
                           Math.abs(points[u][1] - points[v][1]);
                pq.offer(new int[]{dist, v});
            }
        }
    }
    return cost;
}

Classic interview problem! Connect all coordinate points with minimum total cable. Uses Manhattan distance (|x1-x2| + |y1-y2|) as edge weight. It's a complete graph (every point connects to every other), so we compute distances on-the-fly instead of storing adjacency list.

// Kosaraju's Algorithm - O(V + E)
class Kosaraju {
    List> adj;         // Original graph
    List> reverseAdj;  // Reversed graph
    boolean[] visited;                // Track visited vertices
    Stack finishOrder;       // Vertices ordered by finish time
}

Set up data structures for both original and reversed graph. The key insight: we need to process vertices in a specific order (finish time from first DFS), then run DFS on reversed graph. This isolates each SCC.

    List> findSCCs(int n, List> graph) {
        adj = graph;
        visited = new boolean[n];
        finishOrder = new Stack<>();
        
        // Step 1: DFS on original graph, record finish order
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs1(i);
            }
        }
    }
    
    void dfs1(int u) {
        visited[u] = true;
        for (int v : adj.get(u)) {
            if (!visited[v]) dfs1(v);
        }
        finishOrder.push(u);  // Push AFTER all descendants done
    }

First DFS on original graph records "finish times" by pushing to stack after exploring all descendants. Vertices that finish last are pushed last (top of stack). This ordering is crucial - it ensures we process "source" SCCs first in step 3.

        // Step 2: Build reverse graph (flip all edges)
        reverseAdj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            reverseAdj.add(new ArrayList<>());
        }
        for (int u = 0; u < n; u++) {
            for (int v : adj.get(u)) {
                reverseAdj.get(v).add(u);  // Reverse: v -> u
            }
        }

Reverse all edge directions. If original had A→B, reversed has B→A. Why? In reversed graph, you can only reach vertices that could originally reach YOU. Combined with finish order, this traps DFS within each SCC.

        // Step 3: DFS on reverse graph in finish order
        Arrays.fill(visited, false);
        List> sccs = new ArrayList<>();
        
        while (!finishOrder.isEmpty()) {
            int v = finishOrder.pop();  // Process by finish order
            if (!visited[v]) {
                List scc = new ArrayList<>();
                dfs2(v, scc);
                sccs.add(scc);  // Each DFS tree = one SCC!
            }
        }
        
        return sccs;
    }

Process vertices in decreasing finish time (pop from stack). Each DFS on reversed graph explores exactly one SCC - it can't "escape" to other SCCs because edges pointing out are now pointing in, and we process in correct order.

    void dfs2(int u, List scc) {
        visited[u] = true;
        scc.add(u);  // Add to current SCC
        
        for (int v : reverseAdj.get(u)) {
            if (!visited[v]) {
                dfs2(v, scc);
            }
        }
    }
}

Simple DFS that collects all vertices reachable in reversed graph from starting point. Since we process in finish order on reversed graph, all vertices reached in one DFS call form exactly one strongly connected component.

// Count number of SCCs in a directed graph
int countSCCs(int n, List> adj) {
    Kosaraju k = new Kosaraju();
    return k.findSCCs(n, adj).size();
}

Simple wrapper to count SCCs. Each element in the returned list is one SCC. Useful for analyzing graph structure - a graph with 1 SCC means every vertex can reach every other vertex (strongly connected graph).

// Check if graph is bipartite using BFS two-coloring
// Time: O(V + E), Space: O(V)
boolean isBipartite(int[][] graph) {
    int n = graph.length;
    int[] color = new int[n];  // 0 = uncolored, 1 = red, -1 = blue

Method signature and color array initialization. We use a color array where 0 means uncolored, 1 represents red, and -1 represents blue. This allows us to easily assign opposite colors using negation.

    // Handle disconnected components
    for (int start = 0; start < n; start++) {
        if (color[start] != 0) continue;  // Already colored
        
        Queue queue = new LinkedList<>();
        queue.offer(start);
        color[start] = 1;  // Color first vertex red

Loop through all vertices to handle disconnected components. If a vertex is already colored, skip it. Otherwise, initialize a BFS queue and color the starting vertex red (1) to begin the two-coloring process for this component.

        while (!queue.isEmpty()) {
            int u = queue.poll();
            
            for (int v : graph[u]) {
                if (color[v] == 0) {
                    // Uncolored - give opposite color
                    color[v] = -color[u];
                    queue.offer(v);
                } else if (color[v] == color[u]) {
                    // Same color as neighbor - NOT bipartite!
                    return false;
                }
            }
        }
    }

BFS traversal to color all vertices. For each uncolored neighbor, assign the opposite color using negation (-color[u]). If we find a neighbor with the same color as the current vertex, we've detected an odd-length cycle, which means the graph cannot be bipartite.

    return true;  // Successfully two-colored
}

If we successfully color all vertices without any same-color conflicts, the graph is bipartite. All vertices can be divided into two groups where no two vertices in the same group are adjacent.

// Check if graph is bipartite using DFS
boolean isBipartiteDFS(int[][] graph) {
    int n = graph.length;
    int[] color = new int[n];  // 0 = uncolored

Main method signature and initialization. We create a color array where 0 indicates an uncolored vertex. The DFS approach uses recursion instead of an explicit queue to traverse the graph.

    for (int i = 0; i < n; i++) {
        if (color[i] == 0 && !dfs(graph, color, i, 1)) {
            return false;
        }
    }
    
    return true;
}

Iterate through all vertices to handle disconnected components. For each uncolored vertex, start a DFS with color 1 (red). If any DFS returns false (conflict found), the graph is not bipartite. Return true only if all components are successfully two-colored.

boolean dfs(int[][] graph, int[] color, int u, int c) {
    color[u] = c;

DFS helper method that takes the current vertex u and the color c to assign. First, color the current vertex with the given color before exploring its neighbors.

    for (int v : graph[u]) {
        if (color[v] == 0) {
            // Uncolored - try to color with opposite
            if (!dfs(graph, color, v, -c)) {
                return false;
            }
        } else if (color[v] == c) {
            // Same color conflict!
            return false;
        }
    }

Explore all neighbors of the current vertex. If a neighbor is uncolored, recursively try to color it with the opposite color (-c). If the recursive call fails or if a neighbor already has the same color as the current vertex, we've found a conflict indicating an odd cycle.

    return true;
}

If all neighbors are successfully colored without conflicts, return true. This propagates back up the recursion stack, confirming that this subtree of the DFS is bipartite.

// Maximum Bipartite Matching using DFS (Kuhn's Algorithm)
// Given bipartite graph with left vertices [0, m) and right vertices [0, n)
// adj[u] contains neighbors of left vertex u in the right set
class BipartiteMatching {
    int m, n;  // m = left set size, n = right set size
    List> adj;  // Adjacency list for left vertices
    int[] matchL, matchR;  // matchL[u] = right vertex matched to u, matchR[v] = left vertex matched to v
    boolean[] visited;

Class structure for bipartite matching. We maintain two match arrays: matchL[u] stores which right vertex is matched to left vertex u, and matchR[v] stores which left vertex is matched to right vertex v. The visited array prevents revisiting vertices during augmenting path search.

    int maxMatching(int m, int n, List> adj) {
        this.m = m;
        this.n = n;
        this.adj = adj;
        
        matchL = new int[m];
        matchR = new int[n];
        Arrays.fill(matchL, -1);
        Arrays.fill(matchR, -1);
        
        int matching = 0;

Main method initialization. Store graph dimensions and adjacency list. Initialize both match arrays with -1 to indicate all vertices start unmatched. The matching counter will track the total number of matched pairs found.

        // Try to find augmenting path from each unmatched left vertex
        for (int u = 0; u < m; u++) {
            visited = new boolean[n];
            if (dfs(u)) {
                matching++;
            }
        }
        
        return matching;
    }

Iterate through all left vertices and try to find an augmenting path for each. Reset the visited array for each search to allow vertices to be reconsidered. If DFS finds a valid augmenting path, increment the matching count. Return the total number of matched pairs.

    // Try to find augmenting path starting from left vertex u
    boolean dfs(int u) {
        for (int v : adj.get(u)) {
            if (visited[v]) continue;
            visited[v] = true;

DFS helper to find an augmenting path. For each neighbor v of left vertex u, mark it as visited to prevent cycles. Skip already visited vertices during this search iteration.

            // If v is unmatched OR we can find alternate path for v's current match
            if (matchR[v] == -1 || dfs(matchR[v])) {
                matchL[u] = v;
                matchR[v] = u;
                return true;
            }
        }
        
        return false;
    }
}

The key matching logic. If right vertex v is unmatched (matchR[v] == -1), we can directly match u with v. If v is already matched, we recursively try to find an alternate match for v's current partner. If either succeeds, update both match arrays and return true. Return false if no augmenting path exists.

// Example usage: Job Assignment Problem
int maxJobAssignments(int workers, int jobs, int[][] canDo) {
    // canDo[i] = list of jobs worker i can do
    List> adj = new ArrayList<>();
    for (int[] jobList : canDo) {
        adj.add(new ArrayList<>());
        for (int job : jobList) {
            adj.get(adj.size() - 1).add(job);
        }
    }
    
    BipartiteMatching bm = new BipartiteMatching();
    return bm.maxMatching(workers, jobs, adj);
}

Practical example: Job Assignment Problem. Given workers on the left and jobs on the right, where canDo[i] lists jobs that worker i can perform, find the maximum number of job assignments where each worker gets at most one job and each job is assigned to at most one worker.