198. Redundant Connection

🔗 LeetCode Problem: 684. Redundant Connection
📊 Difficulty: Medium
🏷️ Topics: Graph, Union-Find, DFS, Cycle Detection

Problem Statement

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [aᵢ, bᵢ] indicates that there is an edge between nodes aᵢ and bᵢ in the graph.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Example 1:

Input: edges = [[1,2],[1,3],[2,3]]

Output: [2,3]

Explanation:
  Original graph:
    1 --- 2
    |    /
    |   /
    3--/

  The edge [2,3] creates a cycle!
  Removing [2,3] makes it a tree:
    1 --- 2
    |
    3

Example 2:

Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]

Output: [1,4]

Explanation:
  The edge [1,4] creates a cycle: 1→2→3→4→1
  Removing [1,4] makes it a tree.

Constraints: - n == edges.length - 3 <= n <= 1000 - edges[i].length == 2 - 1 <= aᵢ < bᵢ <= edges.length - aᵢ != bᵢ - There are no repeated edges. - The given graph is connected.

---

🌳 Visual Understanding - The Complete Picture

The Problem We're Solving 🤔

Given edges that form a graph with ONE extra edge: 🔗

Key facts:
  ✅ Started as a tree (n nodes, n-1 edges)
  ❌ One extra edge added (now n edges!)
  ⚠️ This creates exactly ONE cycle!

Goal: Find the extra edge (that creates cycle) 🎯

Example:
  edges = [[1,2], [1,3], [2,3]]

  Add edges one by one:
    [1,2]: 1 --- 2  ✅ No cycle
    [1,3]: 1 --- 2  ✅ No cycle
           |
           3
    [2,3]: 1 --- 2  ❌ CYCLE DETECTED!
           |    /
           |   /
           3--/

  Answer: [2,3] (the edge that created cycle!)

Understanding Trees vs Graphs 🌳

Tree properties: 🌳
  ✅ n nodes → n-1 edges (exactly!)
  ✅ Connected (all nodes reachable)
  ✅ No cycles
  ✅ Exactly one path between any two nodes

Example tree (4 nodes, 3 edges):
  1 --- 2
  |
  3 --- 4

Graph with cycle (4 nodes, 4 edges):
  1 --- 2
  |    /
  |   /
  3 --- 4

Extra edge creates cycle! ❌

Why Union-Find is Perfect Here! 🎯

Union-Find naturally detects cycles! 💡

The key insight:
  When adding edge [u, v]:
    If u and v are ALREADY in same set → CYCLE! ❌
    Otherwise → Safe to union ✅

Example:
  edges = [[1,2], [2,3], [1,3]]

  Process [1,2]:
    find(1) = 1, find(2) = 2
    Different sets! Union them ✅

  Process [2,3]:
    find(2) = 1, find(3) = 3
    Different sets! Union them ✅

  Process [1,3]:
    find(1) = 1, find(3) = 1
    SAME SET! Cycle detected! ❌
    Return [1,3] 🎯

Beautiful cycle detection! 🌟

---

🧠 The Journey - Building Intuition

Part 1: Understanding the Problem - "What makes it redundant?" 🤔

💭 Let's think about what "redundant" means!

Tree definition:
  n nodes → EXACTLY n-1 edges
  Any more edges → cycles!

Our problem:
  n nodes → n edges (one too many!)
  Extra edge creates a cycle!

Example with 3 nodes:
  Tree needs: 2 edges
  We have: 3 edges
  Extra: 1 edge (redundant!)

Which edge is redundant?
  The one that completes a cycle! 🎯

Part 2: Adding Edges One by One 📝

💭 Key insight: Process edges in ORDER!

Think of building graph step by step:

Example: [[1,2], [1,3], [2,3]]

Step 1: Add [1,2]
  1 --- 2

  No cycle! ✅

Step 2: Add [1,3]
  1 --- 2
  |
  3

  No cycle! ✅

Step 3: Add [2,3]
  1 --- 2
  |    /
  |   /
  3--/

  CYCLE! ❌

This edge [2,3] is redundant! 🎯

The redundant edge is the FIRST edge that creates a cycle!

Part 3: How to Detect Cycles? 🔍

💭 Union-Find gives us instant cycle detection!

Remember from Problem 195:
  Union-Find tracks which nodes are connected

For cycle detection:
  Before adding edge [u, v]:
    Check: Are u and v already connected?

  If YES → Adding this edge creates cycle! ❌
  If NO → Safe to add ✅

Example:
  edges = [[1,2], [2,3], [1,3]]
  Initially: Sets {1}, {2}, {3}

  Edge [1,2]:
    find(1) = 1, find(2) = 2
    Different! No cycle ✅
    Union: Sets {1,2}, {3}

  Edge [2,3]:
    find(2) = 1, find(3) = 3
    Different! No cycle ✅
    Union: Sets {1,2,3}

  Edge [1,3]:
    find(1) = 1, find(3) = 1
    SAME! They're already connected! ❌
    This edge creates cycle!
    Return [1,3] 🎯

Union-Find makes this O(α(n)) per edge! ⚡

Part 4: Why "Last in Input" Matters 📋

💭 Problem asks for "last" redundant edge in input!

What if multiple edges could be removed?

Example: [[1,2], [2,3], [3,1]]
  Any edge could be removed to break cycle!

  But we want LAST in input order!

  Process in order:
    [1,2]: Add ✅
    [2,3]: Add ✅  
    [3,1]: CYCLE! Return [3,1] (last!) 🎯

By processing edges in input order,
Union-Find naturally finds the last one! ✅

Part 5: The Algorithm - Simple and Elegant! 💡

✨ Complete algorithm:

1. Initialize Union-Find for n nodes

2. For each edge [u, v] in order:

   a. Check if u and v are already connected:
      rootU = find(u)
      rootV = find(v)

   b. If rootU == rootV:
      → Already connected!
      → This edge creates cycle!
      → Return [u, v] 🎯

   c. Otherwise:
      → Not connected yet
      → Union them
      → Continue

3. If we get here, no cycle found
   (But problem guarantees one exists!)

Time: O(n × α(n)) ≈ O(n) ⚡
Space: O(n) 📦

Elegant and efficient! 🌟

---

🎯 Approach 1: Union-Find (Optimal!)

The Key Insight 💡

Use Union-Find for cycle detection 🔗! Process edges in input order 📝. For each edge, check if endpoints already connected using find() 🔍. If same root (connected) → cycle detected, return this edge! ❌ Otherwise, union them ✅. First edge creating cycle = answer! 🎯 Time: O(n × α(n)) ≈ O(n) ⚡, Space: O(n) 📦!

Perfect for cycle detection! 🌟

Complete Implementation

class Solution {
    // ═══════════════════════════════════════════════════════
    // UNION-FIND FOR CYCLE DETECTION 🔗
    // ═══════════════════════════════════════════════════════
    private int[] parent;
    private int[] rank;

    public int[] findRedundantConnection(int[][] edges) {
        // ═══════════════════════════════════════════════════
        // UNION-FIND APPROACH 🌟
        // ═══════════════════════════════════════════════════
        // Process edges in order
        // First edge that connects already-connected nodes = answer!
        // ═══════════════════════════════════════════════════

        int n = edges.length;
        parent = new int[n + 1];  // 1-indexed!
        rank = new int[n + 1];

        // ═══════════════════════════════════════════════════
        // INITIALIZE: Each node is its own set 🏗️
        // ═══════════════════════════════════════════════════
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        // ═══════════════════════════════════════════════════
        // PROCESS EDGES IN ORDER 📝
        // ═══════════════════════════════════════════════════
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];

            // ───────────────────────────────────────────────
            // FIND ROOTS OF BOTH NODES 🔍
            // ───────────────────────────────────────────────
            int rootU = find(u);
            int rootV = find(v);

            // ───────────────────────────────────────────────
            // CHECK FOR CYCLE! 🎯
            // ───────────────────────────────────────────────
            if (rootU == rootV) {
                // ───────────────────────────────────────────
                // ALREADY CONNECTED! ❌
                // This edge creates a cycle!
                // Return this edge (last in input)
                // ───────────────────────────────────────────
                return edge;
            }

            // ───────────────────────────────────────────────
            // NOT CONNECTED YET - UNION THEM ✅
            // ───────────────────────────────────────────────
            union(rootU, rootV);
        }

        // Should never reach here (problem guarantees cycle exists)
        return new int[]{};
    }

    // ═══════════════════════════════════════════════════════
    // FIND: Get root with path compression ⚡
    // ═══════════════════════════════════════════════════════
    private int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // Path compression!
        }
        return parent[x];
    }

    // ═══════════════════════════════════════════════════════
    // UNION: Merge two sets with union by rank 📊
    // ═══════════════════════════════════════════════════════
    private void union(int x, int y) {
        if (rank[x] < rank[y]) {
            parent[x] = y;
        } else if (rank[x] > rank[y]) {
            parent[y] = x;
        } else {
            parent[y] = x;
            rank[x]++;
        }
    }
}

Why This Works 🎯

Union-Find detects cycles naturally: 🔗 - If find(u) == find(v): already connected! - Adding edge would create cycle! - This is our redundant edge!

Processing in order gives "last": 📝 - We process edges in input order - First edge that causes cycle = last redundant edge in input - Return immediately when cycle detected!

Optimizations make it fast: ⚡ - Path compression: O(α(n)) find operations - Union by rank: keeps trees balanced - Overall: nearly O(1) per edge!

---

🎯 Approach 2: DFS (Alternative)

The Key Insight 💡

Build graph gradually with DFS cycle detection 🌊. For each edge, check if path already exists between endpoints using DFS 🔍. If path exists → cycle! ❌ Otherwise, add edge to graph ✅. Time: O(n²) ⚡, Space: O(n) 📦!

More intuitive but slower! 🌟

Complete Implementation

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        // ═══════════════════════════════════════════════════
        // DFS APPROACH - CYCLE DETECTION 🌊
        // ═══════════════════════════════════════════════════
        // Build graph incrementally
        // Check for cycle before adding each edge
        // ═══════════════════════════════════════════════════

        int n = edges.length;
        List<List<Integer>> graph = new ArrayList<>();

        // Initialize graph
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // ═══════════════════════════════════════════════════
        // PROCESS EDGES ONE BY ONE 📝
        // ═══════════════════════════════════════════════════
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];

            // ───────────────────────────────────────────────
            // CHECK IF PATH EXISTS: u -> v? 🔍
            // ───────────────────────────────────────────────
            boolean[] visited = new boolean[n + 1];

            if (hasPath(u, v, graph, visited)) {
                // ───────────────────────────────────────────
                // PATH EXISTS! Adding edge creates cycle! ❌
                // ───────────────────────────────────────────
                return edge;
            }

            // ───────────────────────────────────────────────
            // NO PATH - SAFE TO ADD EDGE ✅
            // ───────────────────────────────────────────────
            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        return new int[]{};
    }

    // ═══════════════════════════════════════════════════════
    // DFS: Check if path exists from source to target 🔍
    // ═══════════════════════════════════════════════════════
    private boolean hasPath(int source, int target, 
                           List<List<Integer>> graph, boolean[] visited) {
        // ───────────────────────────────────────────────────
        // BASE CASE: Reached the target! 🎯
        // ───────────────────────────────────────────────────
        // This checks: "Am I at the destination node?"
        // If YES → Path exists! We found it! ✅
        // ───────────────────────────────────────────────────
        if (source == target) {
            return true;  // Found path! ✅
        }

        visited[source] = true;

        for (int neighbor : graph.get(source)) {
            if (!visited[neighbor]) {
                if (hasPath(neighbor, target, graph, visited)) {
                    return true;
                }
            }
        }

        return false;  // No path found
    }
}

Understanding source == target 🤔

💭 Why do we check "source == target"?

The function asks: "Is there a path from source to target?"

The base case "source == target" means:
  "I've REACHED the target node!" 🎯
  "Path exists! Return true!" ✅

Let's trace through an example...

╔══════════════════════════════════════════════════════════╗
║  EXAMPLE: Why we need source == target check            ║
╚══════════════════════════════════════════════════════════╝

Current graph:
  1 --- 2
        |
        3

Try adding edge [1, 3]:
  Question: Does path exist from 1 to 3?

DFS Trace: hasPath(1, 3, graph, visited)

Step 1: hasPath(1, 3)
  source = 1, target = 3
  1 == 3? NO ❌ (not at target yet)
  visited[1] = true
  neighbors of 1: [2]

  Try neighbor 2:

Step 2: hasPath(2, 3)  
  source = 2, target = 3
  2 == 3? NO ❌ (not at target yet)
  visited[2] = true
  neighbors of 2: [1, 3]
  (skip 1, already visited)

  Try neighbor 3:

Step 3: hasPath(3, 3)
  source = 3, target = 3
  3 == 3? YES! ✅✅✅

  🎯 WE REACHED THE TARGET!
  This is the SUCCESS condition!
  Return TRUE!

← Step 2 returns TRUE (found through neighbor 3)
← Step 1 returns TRUE (found through neighbor 2)

RESULT: Path exists 1→2→3! ❌
Don't add edge [1,3] - would create cycle!

The source == target check is HOW WE KNOW we found it! 🎯

Complete Visual Trace 🔍

╔═══════════════════════════════════════════════════════╗
║         CALL STACK VISUALIZATION                     ║
╚═══════════════════════════════════════════════════════╝

Graph: 1 --- 2 --- 3

Question: Path from 1 to 3?

hasPath(1, 3):
  │
  ├─ Check: 1 == 3? NO ❌
  │   → Not at destination yet, keep searching
  │
  ├─ Mark visited[1] = true
  │
  └─ Try neighbor 2:
      │
      hasPath(2, 3):
        │
        ├─ Check: 2 == 3? NO ❌  
        │   → Still not there, keep going
        │
        ├─ Mark visited[2] = true
        │
        └─ Try neighbor 3:
            │
            hasPath(3, 3):
              │
              ├─ Check: 3 == 3? YES! ✅
              │   → FOUND IT! We're AT the target!
              │   → This is the base case!
              │
              └─ return TRUE

            ← Returns TRUE to caller

        ← Returns TRUE to caller

    ← Returns TRUE to caller

Final answer: Path exists! ✅

What if we DIDN'T have this check? ❌

Without "source == target" check:

hasPath(3, 3):  // Reached node 3
  // No base case to recognize we found it!

  visited[3] = true
  neighbors of 3: [2]

  Try neighbor 2:
    Already visited! Skip.

  No more neighbors.
  return FALSE ❌❌❌

WRONG! We DID reach node 3 but didn't recognize it!

The "source == target" check explicitly says:
  "Hey! I'm AT the target node right now!"
  "That means I found the path!" ✅

Without it, we'd be AT the destination but not realize it! 🎯

Comparison: Found vs Not Found 🔍

CASE 1: Path EXISTS
  Graph: 1 --- 2 --- 3
  Query: hasPath(1, 3)

  DFS will eventually call hasPath(3, 3)
  3 == 3? YES! ✅ Return TRUE

  The base case triggers! Success! 🎯

CASE 2: Path DOESN'T EXIST
  Graph: 1 --- 2     4 --- 5
              |
              3
  Query: hasPath(1, 5)

  DFS explores: 1 → 2 → 3
  Never reaches node 5!
  Never triggers "source == target"

  Eventually all neighbors exhausted
  Return FALSE ✅

  No base case triggered = no path! 😞

The "source == target" check is the ONLY way
DFS knows it successfully found the target! 🔑

Think of it Like a Treasure Hunt 🗺️

You're looking for treasure at location X:

source = your current location
target = treasure location X

As you explore:
  Check: "Am I at location X?" (source == target?)

  If YES → Found treasure! ✅ Success!
  If NO → Keep exploring neighbors

Without this check:
  You could be STANDING on the treasure
  But not realize you found it! ❌

The check is essential:
  It's how you recognize SUCCESS! 🎯

Why This Works 🎯

DFS checks for existing path: 🌊 - Before adding edge [u,v], DFS checks if path exists - If path exists: adding edge creates alternate path (cycle!) - If no path: safe to add

Incremental graph building: 🏗️ - Build graph edge by edge - Check before each addition - Natural cycle detection!

Slower but more intuitive: 📊 - Each DFS: O(n) time - n edges: O(n²) total - But easier to understand!

---

🔍 Detailed Dry Run - Union-Find Approach

Let's trace on:

edges = [[1,2],[1,3],[2,3]]

╔══════════════════════════════════════════════════════════════╗
║                       INITIALIZATION                         ║
╚══════════════════════════════════════════════════════════════╝

n = 3 (three edges, so three nodes)

Initialize Union-Find:
  parent = [_, 1, 2, 3]  // Index 0 unused (1-indexed)
  rank   = [_, 0, 0, 0]

Sets: {1}, {2}, {3}  (all separate)

Visual:
  1    2    3

╔══════════════════════════════════════════════════════════════╗
║                    PROCESS EDGES IN ORDER                    ║
╚══════════════════════════════════════════════════════════════╝

╔═════════════════════════════════════════════════╗
║ EDGE 1: [1, 2]                                  ║
╠═════════════════════════════════════════════════╣
║                                                 ║
║ Check if 1 and 2 are connected:                ║
║   rootU = find(1) = 1                          ║
║   rootV = find(2) = 2                          ║
║                                                 ║
║ rootU == rootV? (1 == 2?)                      ║
║   NO! Different sets! ✅                       ║
║                                                 ║
║ No cycle! Union them:                           ║
║   union(1, 2)                                   ║
║   rank[1] == rank[2] (both 0)                  ║
║   parent[2] = 1                                ║
║   rank[1]++  (0 → 1)                           ║
║                                                 ║
║ Result:                                         ║
║   parent = [_, 1, 1, 3]                        ║
║   rank   = [_, 1, 0, 0]                        ║
║                                                 ║
║ Visual:                                         ║
║     1                                           ║
║     ↑                                           ║
║     2         3                                 ║
║                                                 ║
║ Sets: {1, 2}, {3}                              ║
╚═════════════════════════════════════════════════╝

╔═════════════════════════════════════════════════╗
║ EDGE 2: [1, 3]                                  ║
╠═════════════════════════════════════════════════╣
║                                                 ║
║ Check if 1 and 3 are connected:                ║
║   rootU = find(1) = 1                          ║
║   rootV = find(3) = 3                          ║
║                                                 ║
║ rootU == rootV? (1 == 3?)                      ║
║   NO! Different sets! ✅                       ║
║                                                 ║
║ No cycle! Union them:                           ║
║   union(1, 3)                                   ║
║   rank[1] = 1, rank[3] = 0                     ║
║   rank[1] > rank[3]                            ║
║   parent[3] = 1                                ║
║                                                 ║
║ Result:                                         ║
║   parent = [_, 1, 1, 1]                        ║
║   rank   = [_, 1, 0, 0]                        ║
║                                                 ║
║ Visual:                                         ║
║       1                                         ║
║      / \                                        ║
║     2   3                                       ║
║                                                 ║
║ Sets: {1, 2, 3}  (all connected!)              ║
╚═════════════════════════════════════════════════╝

╔═════════════════════════════════════════════════╗
║ EDGE 3: [2, 3]                                  ║
╠═════════════════════════════════════════════════╣
║                                                 ║
║ Check if 2 and 3 are connected:                ║
║   rootU = find(2):                             ║
║     parent[2] = 1                              ║
║     parent[1] = 1 ✅ (root!)                   ║
║     return 1                                    ║
║                                                 ║
║   rootV = find(3):                             ║
║     parent[3] = 1                              ║
║     parent[1] = 1 ✅ (root!)                   ║
║     return 1                                    ║
║                                                 ║
║ rootU == rootV? (1 == 1?)                      ║
║   YES! SAME ROOT! ❌                           ║
║                                                 ║
║ ⚠️ CYCLE DETECTED! ⚠️                          ║
║                                                 ║
║ 2 and 3 are ALREADY CONNECTED through 1!       ║
║ Adding edge [2,3] creates a cycle:              ║
║                                                 ║
║   Before [2,3]:      After [2,3]:              ║
║       1                   1                     ║
║      / \                 / \                    ║
║     2   3               2---3  ← Cycle!        ║
║                                                 ║
║ RETURN [2, 3] 🎯                                ║
║                                                 ║
╚═════════════════════════════════════════════════╝

╔══════════════════════════════════════════════════════════════╗
║                    FINAL RESULT: [2, 3]                      ║
╠══════════════════════════════════════════════════════════════╣
║                                                              ║
║  The edge [2, 3] is redundant because:                      ║
║    • Node 2 is connected to node 1                          ║
║    • Node 3 is connected to node 1                          ║
║    • So 2 and 3 are already connected through 1!            ║
║    • Adding direct edge 2↔3 creates cycle                   ║
║                                                              ║
║  Removing [2, 3] leaves a tree:                             ║
║       1                                                      ║
║      / \                                                     ║
║     2   3                                                    ║
║                                                              ║
║  Perfect tree: 3 nodes, 2 edges! ✅                         ║
║                                                              ║
╚══════════════════════════════════════════════════════════════╝

🔑 Key Observations:

1. Union-Find tracks connectivity: 🔗 After first two edges, all three nodes connected through node 1

2. Third edge creates cycle: ❌ Nodes 2 and 3 already have path through 1

3. find() reveals connection: 🔍 Both have same root (1), so already in same set

4. Immediate detection: ⚡ No need to search entire graph, Union-Find knows instantly!

5. Last in input returned: 📝 [2,3] is the last edge, which causes the cycle

---

📊 Complexity Analysis

Union-Find Approach

Time Complexity: O(n × α(n)) ≈ O(n) ⚡

Where:
  n = number of edges
  α(n) = inverse Ackermann function

For each edge: O(α(n))
  find(u): O(α(n)) with path compression
  find(v): O(α(n)) with path compression
  union: O(1) after finds

Total: n edges × O(α(n)) = O(n × α(n))

Since α(n) ≤ 5 for all practical n:
  Effectively O(n)! ⚡

Example: n = 1000
  Operations: ~5000 (very fast!) ✅

Space Complexity: O(n) 📦

Parent array: O(n)
Rank array: O(n)

Total: O(n) 📦

Very efficient! ✨

DFS Approach

Time Complexity: O(n²) 📊

For each edge: O(n)
  DFS traversal: O(V + E) = O(n) worst case
  (Before adding ith edge, graph has i-1 edges)

Total: O(n) edges × O(n) DFS = O(n²)

Example: n = 1000
  Operations: ~1,000,000 (slower) ❌

Still acceptable but slower than Union-Find!

Space Complexity: O(n) 📦

Graph adjacency list: O(n)
Visited array: O(n)
Recursion stack: O(n)

Total: O(n) 📦

---

🔗 Related Problems & Pattern

Union-Find Cycle Detection Pattern 🎯

// Template for cycle detection with Union-Find
class Solution {
    private int[] parent;
    private int[] rank;

    public EdgeType detectCycle(Edge[] edges) {
        int n = edges.length;
        parent = new int[n + 1];
        rank = new int[n + 1];

        // Initialize
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        // Process edges in order
        for (Edge edge : edges) {
            int u = edge.from;
            int v = edge.to;

            int rootU = find(u);
            int rootV = find(v);

            // CYCLE DETECTION! 🔑
            if (rootU == rootV) {
                return edge;  // This edge creates cycle!
            }

            union(rootU, rootV);
        }

        return null;  // No cycle
    }

    private int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    private void union(int x, int y) {
        if (rank[x] < rank[y]) {
            parent[x] = y;
        } else if (rank[x] > rank[y]) {
            parent[y] = x;
        } else {
            parent[y] = x;
            rank[x]++;
        }
    }
}

When to Use This Pattern 🎯

✅ Perfect for:
  • "Find redundant connection/edge"
  • "Detect cycle in undirected graph"
  • "Remove one edge to make tree"
  • "Build minimum spanning tree"
  • "Check if adding edge creates cycle"

🔍 Recognition keywords:
  • "Redundant"
  • "Extra edge"
  • "Creates cycle"
  • "Remove to make tree"
  • "Process edges one by one"

📊 Why Union-Find wins:
  • O(α(n)) per edge (nearly O(1))
  • No graph building needed
  • Direct cycle detection
  • Elegant and simple

Related LeetCode Problems 📚

Direct Applications:

1. Graph Valid Tree (LC 261) - Medium 🌳 • What's similar: Check for cycles, tree validation 🔍 • What's different: Check if valid tree (not find redundant) ✅ • Key insight: Tree: n nodes, n-1 edges, no cycles! 🎯

2. Number of Connected Components (LC 323) - Medium 🔗 • What's similar: Union-Find to count components 📊 • What's different: No cycle detection needed ✅ • Key insight: Count leaders in Union-Find! 🎯

3. Redundant Connection II (LC 685) - Hard 🔄 • What's similar: Find redundant edge in graph 🔍 • What's different: DIRECTED graph (more complex!) ⚠️ • Key insight: Handle in-degree violations! 💡

4. Accounts Merge (LC 721) - Medium 📧 • What's similar: Union-Find to merge groups 🤝 • What's different: Merging based on common emails ✅ • Key insight: Union-Find for grouping! 🎯

---

📝 Quick Revision Notes

🎯 Core Concept

Redundant Connection finds edge that creates cycle in graph 🔗. Use Union-Find for cycle detection 🎯! Process edges in order 📝. For each edge [u,v], check if find(u) == find(v) 🔍. If same root → already connected → adding edge creates cycle! ❌ Return this edge (last redundant)! Otherwise union them ✅. Time: O(n × α(n)) ≈ O(n) ⚡, Space: O(n) 📦! Union-Find makes cycle detection O(1)! 🚀

⚡ Quick Implementation

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class Solution {
  public int[] findRedundantConnection(int[][] edges) {
    // // Approach 1 - DFS
    // return dfs(edges);

    // Approach 2 - Union Find
    return unionFind(edges);
  }

  private int[] unionFind(int[][] edges) {
    // Step 1: initialize (parents as themselves and zero ranks).
    int len = edges.length;
    int[] parent = new int[len + 1];
    int[] rank = new int[len + 1];

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

    for (int[] edge : edges) {
      int rootX = find(edge[0], parent);
      int rootY = find(edge[1], parent);

      if (rootX == rootY) {
        return edge;
      }

      union(rootX, rootY, parent, rank);
    }

    return new int[] {};
  }

  private void union(int x, int y, int[] parent, int[] rank) {
    if (rank[x] < rank[y]) {
      parent[x] = y;
    } else if (rank[x] > rank[y]) {
      parent[y] = x;
    } else {
      parent[y] = x;
      rank[x]++;
    }
  }

  private int find(int i, int[] parent) {
    if (parent[i] != i) {
      parent[i] = find(parent[i], parent);
    }

    return parent[i];
  }

  private int[] dfs(int[][] edges) {
    // Step 1: start creating graph from vertices.
    List<List<Integer>> graph = new ArrayList<>();

    // Initializing.
    for (int i = 0; i <= edges.length; i++) {
      graph.add(new ArrayList<>());
    }

    // Start addding edges one by one.
    for (int[] edge : edges) {
      // GOTCHA: we need to reinitialize visited set every loop.
      // If not, 1 -> 2 makes visited: {1, 2} and when edge 1 -> 3 comes,
      // since 1 and 3 are already in visited set, never gets added and
      // always return an empty array.
      HashSet<Integer> visited = new HashSet<>();
      // before adding check if there is a path already that exists between
      // edge[0] and edge[1] that makes the graph cyclic.
      if (hasPathExist(edge[0], edge[1], graph, visited)) {
        return edge;
      }

      // If not add the edge to the graph and proceed next.
      graph.get(edge[0]).add(edge[1]);
      graph.get(edge[1]).add(edge[0]);
    }

    return new int[] {};
  }

  private boolean hasPathExist(int source, int destination, List<List<Integer>> graph, HashSet<Integer> visited) {
    // Means I have destination reached from source. There
    // exists a path and have to return true.
    if (source == destination) {
      return true;
    }

    visited.add(source);

    for (int neighbour : graph.get(source)) {
      if (!visited.contains(neighbour)) {
        if (hasPathExist(neighbour, destination, graph, visited)) {
          return true;
        }
      }
    }

    return false;
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    System.out.println(Arrays.toString(s.findRedundantConnection(new int[][] { { 1, 2 }, { 1, 3 }, { 2, 3 } })));
    System.out.println(
        Arrays.toString(s.findRedundantConnection(new int[][] { { 1, 2 }, { 2, 3 }, { 3, 4 }, { 1, 4 }, { 1, 5 } })));
  }
}

🔑 Key Insights

Cycle Detection with Union-Find: 🔑

The brilliant insight:

Before adding edge [u, v]:
  Check: Are u and v already connected?

How? Find their roots!
  rootU = find(u)
  rootV = find(v)

If rootU == rootV:
  → They're in SAME set!
  → Already connected!
  → Adding edge creates alternate path (cycle!) ❌

If rootU != rootV:
  → Different sets
  → Not connected yet
  → Safe to add edge ✅
  → Union them

Example:
  Graph: 1 --- 2
         |
         3

  Sets: {1, 2, 3} (all connected through 1)

  Try adding [2, 3]:
    find(2) = 1
    find(3) = 1
    Same root! Already connected through 1!
    Adding [2,3] creates triangle (cycle!)

    1 --- 2
    |    /
    |   /
    3--/  ← Cycle!

Union-Find detects this instantly! ⚡

Why Process in Input Order: 📝

Problem requirement: Return LAST redundant edge

How we achieve it:
  Process edges in input order
  Return FIRST edge that creates cycle

This first edge that creates cycle IS the last redundant edge!

Example:
  edges = [[1,2], [2,3], [3,1]]

  All three edges form cycle
  But which to remove?

  Process order:
    [1,2]: Add ✅
    [2,3]: Add ✅
    [3,1]: Cycle! ❌ Return [3,1]

  [3,1] is LAST in input, as required! 🎯

By processing in order, we naturally find last! ✅

Tree Properties Reminder: 🌳

Valid tree requirements:

1. n nodes → n-1 edges (exactly!) 🔢
   More edges → has cycle
   Fewer edges → disconnected

2. Connected (all reachable) 🔗

3. No cycles 🔄

Our problem:
  ✅ Connected (guaranteed)
  ❌ n nodes, n edges (one too many!)
  ❌ Has exactly ONE cycle

Goal: Remove the one extra edge! 🎯

Union-Find vs DFS: ⚖️

Union-Find approach:
  ✅ O(n × α(n)) ≈ O(n) time
  ✅ Direct cycle detection
  ✅ No graph building
  ✅ Clean and elegant
  ⭐ Recommended!

DFS approach:
  ❌ O(n²) time
  ✅ More intuitive
  ✅ Explicit path checking
  📊 Good for understanding

For this problem:
  Union-Find is superior! 🏆

But DFS helps build intuition:
  "Is there already a path between u and v?"
  If yes → adding edge creates cycle!

Union-Find answers same question faster! ⚡

🎪 Memory Aid

"Check before you connect" 🔍
"Same root means cycle direct" 🔗
"Return edge that makes it incorrect" ❌
"Union-Find detects it, perfect!" 🎯 ✨

⚠️ Don't Forget

• 1-indexed nodes - use arrays of size n+1! 🔢
• Check roots, not nodes - find(u) vs u! 🔍
• Return edge immediately - when cycle detected! ⚡
• Process in order - for "last" requirement! 📝
• Path compression - for O(α(n)) performance! 🚀
• Union by rank - keeps trees balanced! 📊

---

🎉 Congratulations!

You've mastered Cycle Detection with Union-Find! 🌟

What You Learned:

✅ Cycle detection - instant with Union-Find! 🔗
✅ Same root check - if find(u) == find(v) → cycle! 🔍
✅ Processing order - return last redundant naturally! 📝
✅ Tree properties - n nodes need n-1 edges! 🌳
✅ Pattern application - Union-Find for dynamic graphs! 🎯

The Beautiful Pattern:

Union-Find Cycle Detection Pattern:

For each edge [u, v]:
  1. Find roots: rootU = find(u), rootV = find(v)
  2. Check: if rootU == rootV → CYCLE! ❌
  3. Otherwise: union(rootU, rootV) ✅

This pattern solves:
  ✅ Redundant connection detection
  ✅ Tree validation
  ✅ MST construction (Kruskal's)
  ✅ Dynamic graph connectivity
  ✅ All cycle detection problems

Master this = Master Union-Find! 🔑

Union-Find becomes more powerful with each problem! 🚀
Cycle detection is your second superpower! 💪✨🎯