Cycle Detection Using Disjoint-Set Union

Welcome back! In our last lesson, you built a fully optimized Disjoint-Set Union (DSU) data structure from the ground up. You now have a powerful tool for managing connections between elements, complete with path compression and union by size. Today, we'll immediately put that tool to use to solve its most classic application: detecting cycles in an undirected graph.

This lesson directly addresses the learning outcome of using DSU to determine if adding an edge creates a cycle. We will explore the simple yet profound logic that makes DSU perfect for this task. By the end of our session, you'll be able to confidently implement this pattern in TypeScript, a fundamental skill for solving a wide range of graph-based interview problems.

Let's briefly recall the core of your DisjointSet class: it groups elements into components, and for any element, the find method returns a unique "representative" for its component. This is the only mechanism we'll need.

The Core Idea: What is a Cycle in DSU Terms?

Imagine you have a graph and you're adding edges one by one. When does adding a new edge, say between nodes u and v, create a cycle? It creates a cycle if and only if there was already a path between u and v before you added the new edge. The new edge simply completes the loop.

This is where DSU shines. How can we tell if there's already a path between u and v? We can check if they belong to the same connected component. Using the DSU data structure you built, this check is incredibly simple: u and v are in the same component if their representatives are the same.

Therefore, the algorithm for cycle detection is:

1. Initialize a DSU structure with one component for each node in the graph.
2. Iterate through each edge (u, v) you want to add.
3. Before adding the edge, check if u and v are already connected by calling find(u) and find(v).
4. If find(u) equals find(v), they are already in the same component. Adding this edge would create a cycle. You've found one!
5. If they are in different components, they are not yet connected. Perform a union(u, v) operation to merge their components, signifying that you've added the edge and connected them.

The following video explains this exact process. It uses a graph and visually demonstrates how processing each edge and checking for common parents (representatives) leads to cycle detection.

A Visual Walkthrough

Let's trace this algorithm with a concrete example. The image below perfectly illustrates the process step-by-step. We have 4 nodes (0, 1, 2, 3) and we will process the edges (0,1), (1,2), (2,3), and (3,0) in order.

Let's follow the trace:

1. Process edge (0, 1):

   • find(0) returns 0. find(1) returns 1. They are different.
   • This means nodes 0 and 1 are in different components. Adding this edge does not create a cycle.
   • We perform union(0, 1), merging their sets. Node 0 is attached to node 1, making 1 the representative.

2. Process edge (1, 2):

   • find(1) returns 1. find(2) returns 2. They are different.
   • No cycle is created.
   • We perform union(1, 2). Node 2 is attached to node 1. The representative of the component {0, 1, 2} is now 1.

3. Process edge (2, 3):

   • find(2) (which is 1) and find(3) (which is 3) are different.
   • No cycle is created.
   • We perform union(2, 3). Node 3 is attached to the representative of its component, which is 1. Now all nodes {0, 1, 2, 3} are in a single component with 1 as the representative. (Note: The image attaches 3 under 2, which then points to 1. Path compression, which you implemented, would eventually flatten this, but the connectivity result is the same).

4. Process edge (3, 0):

   • find(3) returns 1. find(0) also returns 1. They are the same!
   • This is the critical moment. Because both nodes already belong to the same component, there must be an existing path connecting them (e.g., 0 → 1 ← 2 ← 3).
   • Adding the edge (3, 0) creates a cycle. The algorithm correctly detects it and can stop.

From Logic to Code

Now, let's implement this logic in TypeScript. We will use the DisjointSet class you created in the previous lesson. Here's a function that takes the number of nodes and a list of edges and returns true if a cycle is detected, and false otherwise.

// Assuming the DisjointSet class from the previous lesson is available:
/*
class DisjointSet {
    private parent: number[];
    private size: number[];
    private numComponents: number;

    constructor(n: number) { ... }
    find(i: number): number { ... }
    union(i: number, j: number): boolean { ... }
    isConnected(i: number, j: number): boolean { ... }
    getComponentCount(): number { ... }
}
*/

/**
 * Detects if a cycle exists in an undirected graph.
 * @param n The number of nodes in the graph, labeled 0 to n-1.
 * @param edges An array of edges, where each edge is a pair [u, v].
 * @returns true if a cycle is present, false otherwise.
 */
function hasCycle(n: number, edges: number[][]): boolean {
    // 1. Initialize the DSU with n separate components.
    const ds = new DisjointSet(n);

    // 2. Iterate through each edge.
    for (const [u, v] of edges) {
        // 3. Find the representatives for both nodes.
        const rootU = ds.find(u);
        const rootV = ds.find(v);

        // 4. If they are the same, a cycle is detected.
        if (rootU === rootV) {
            console.log(`Cycle detected when trying to add edge (${u}, ${v})`);
            return true;
        }

        // 5. Otherwise, unite the components.
        ds.union(u, v);
    }

    // If the loop completes, no cycles were found.
    return false;
}

// --- Example Usage ---
const n = 4;
const edgesWithCycle = [[0, 1], [1, 2], [2, 3], [3, 0]];
console.log(`Graph has cycle: ${hasCycle(n, edgesWithCycle)}`); // true

const edgesWithoutCycle = [[0, 1], [1, 2], [2, 3]];
console.log(`Graph has cycle: ${hasCycle(n, edgesWithoutCycle)}`); // false

This implementation directly maps to the logic we've discussed. It's clean, efficient, and leverages the power of the DSU you've already mastered.

Application: The "Graph Valid Tree" Problem

A very common interview problem that builds on this concept is "Graph Valid Tree" (LeetCode 261). A valid tree is an undirected graph that satisfies two conditions:

1. It has no cycles.
2. It is fully connected (i.e., it consists of a single component).

You now know how to check for the first condition! To check for the second, you can use the getComponentCount() method from your DSU class. After processing all edges, if the graph is a single connected component, getComponentCount() will return 1.

The following reading provides a great explanation of how to solve the "Graph Valid Tree" problem. It uses a slightly different DSU implementation style but the core concepts are identical.

By combining these two checks—no cycles and a single final component—you can robustly determine if a given graph is a valid tree.

Conclusion

In this lesson, we put your DSU data structure into practice, showing how it provides an elegant and highly efficient solution for detecting cycles in a graph.

Here are the key takeaways:

• The Core Logic: An edge (u, v) creates a cycle if nodes u and v are already in the same connected component.
• The DSU Algorithm: To detect a cycle, iterate through the graph's edges. For each edge (u, v), if find(u) === find(v), you've found a cycle. Otherwise, perform a union(u, v).
• Beyond Cycle Detection: By adding a final check to ensure there is only one component (ds.getComponentCount() === 1), you can solve the "Graph Valid Tree" problem.

You've now mastered a crucial pattern for problems involving graph connectivity. This concludes our module on greedy algorithms and connectivity. We are about to make a significant shift in topics. In the next module, we will dive into one of the most powerful paradigms in algorithms: Dynamic Programming. Don't let its reputation intimidate you; we will build it up from first principles, step-by-step, to make it intuitive and approachable.