Redundant Connection

Imagine a group of people, and you keep drawing lines to connect them. At some point you draw one line too many, and a loop forms. Redundant Connection asks you to find that one extra line. This is the classic first question for a data structure called union-find, and once you learn it here you will spot it in many graph problems.

🎯 The Problem

You start with a tree, then someone adds one extra edge, and you must find that extra edge.

• A tree is a set of nodes connected with no loops, where everything is reachable.
• One extra edge is added. It creates exactly one cycle.
• You get all the edges and must return the one edge that, if removed, leaves a valid tree again.
• If more than one answer could work, return the edge that appears last in the input.

For edges [[1,2],[1,3],[2,3]], the first two connect 1-2 and 1-3, which is fine. The third edge 2-3 joins two nodes already connected through 1. That closes a loop. So [2,3] is the redundant edge.

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

Explanation: 1-2 and 1-3 form a tree. The edge 2-3 closes a cycle.

Here is the graph. Notice how the three edges form a triangle, which is a loop.

🐢 Approach 1: DFS Connection Check (Brute Force)

We add edges one by one and check for a loop before each add.

The idea:

• Before adding an edge, ask if its two nodes are already connected.
• To check, run a depth-first search. That means follow paths from one node to see if you can reach the other.
• If they are already reachable, this edge would form a loop. So it is the answer.

How it works:

• Build the graph edge by edge.
• For each new edge, search from one end to the other before adding it.

Why it is weak:

• Every connection check walks across the graph again.
• For each edge you may scan the whole graph.
• That gets slow when the graph is large.

Here is the DFS-before-union code:

def find_redundant_connection(edges):
    graph = {}
    def connected(a, b, seen):
        if a == b: return True
        seen.add(a)
        return any(nei not in seen and connected(nei, b, seen) for nei in graph.get(a, []))
    for a, b in edges:
        if a in graph and b in graph and connected(a, b, set()):
            return [a, b]
        graph.setdefault(a, []).append(b); graph.setdefault(b, []).append(a)

⚡ Approach 2: Union-Find (Best)

The idea in one line: keep each group of connected nodes together, and the first edge that joins two nodes already in the same group is the answer.

The idea:

• Union-find tracks which group each node belongs to and merges two groups fast. It is also called a disjoint set, because groups never overlap.
• It keeps one array called parent. Follow the parents up and you reach the top node of the group, called the root.
• Two nodes are in the same group when they share the same root.

How it works:

• find(x) follows the parent links up until it reaches the root.
• union(a, b) joins two groups by pointing one root at the other.
• Go through the edges in order. For each edge [a, b], find both roots.
• If they already share a root, this edge closes a cycle, so return it.
• Otherwise union the two nodes and continue.

Why it is fast:

• Path compression points each node on the find path straight at the root, so the next lookup is shorter.
• Union by rank attaches the shorter group under the taller one, keeping the trees flat.
• Together these make every find or union run in almost constant time.

Here is how find with path compression flattens a chain. Before, node 3 points to 2, which points to 1. After, both point straight to the root 1.

Steps to Solve

1. Create a parent array where every node starts as its own parent, and a rank array of zeros.
2. Write find(x) that walks up to the root and points each node along the way straight to the root.
3. Write union(a, b) that finds both roots and attaches the lower-rank root under the higher-rank one.
4. Go through the edges in the given order.
5. For each edge [a, b], find both roots. If they match, return this edge, because it closes a cycle.
6. If the roots differ, union the two nodes and move to the next edge.

#include <stdio.h>

#define MAXN 1001

int parent[MAXN];
int rnk[MAXN];

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

int unite(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return 0;           // already connected
    if (rnk[ra] < rnk[rb]) {          // union by rank
        parent[ra] = rb;
    } else if (rnk[ra] > rnk[rb]) {
        parent[rb] = ra;
    } else {
        parent[rb] = ra;
        rnk[ra]++;
    }
    return 1;
}

int main(void) {
    int edges[][2] = {{1, 2}, {1, 3}, {2, 3}};
    int m = 3;

    for (int i = 1; i < MAXN; i++) { parent[i] = i; rnk[i] = 0; }

    int ansA = -1, ansB = -1;
    for (int i = 0; i < m; i++) {
        int a = edges[i][0], b = edges[i][1];
        if (!unite(a, b)) {           // edge closes a cycle
            ansA = a; ansB = b;
            break;
        }
    }

    printf("[%d, %d]\n", ansA, ansB);
    return 0;
}

[2, 3]

#include <iostream>
#include <vector>
using namespace std;

vector<int> parent, rnk;

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

bool unite(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return false;        // already connected
    if (rnk[ra] < rnk[rb]) parent[ra] = rb;       // union by rank
    else if (rnk[ra] > rnk[rb]) parent[rb] = ra;
    else { parent[rb] = ra; rnk[ra]++; }
    return true;
}

vector<int> redundant(vector<vector<int>>& edges) {
    int n = edges.size();
    parent.assign(n + 1, 0);
    rnk.assign(n + 1, 0);
    for (int i = 0; i <= n; i++) parent[i] = i;

    for (auto& e : edges) {
        if (!unite(e[0], e[1])) return e;  // closes a cycle
    }
    return {};
}

int main() {
    vector<vector<int>> edges = {{1, 2}, {1, 3}, {2, 3}};
    vector<int> ans = redundant(edges);
    cout << "[" << ans[0] << ", " << ans[1] << "]" << endl;
    return 0;
}

[2, 3]

import java.util.Arrays;

public class RedundantConnection {
    static int[] parent;
    static int[] rank;

    static int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // path compression by halving
            x = parent[x];
        }
        return x;
    }

    static boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;        // already connected
        if (rank[ra] < rank[rb]) parent[ra] = rb;       // union by rank
        else if (rank[ra] > rank[rb]) parent[rb] = ra;
        else { parent[rb] = ra; rank[ra]++; }
        return true;
    }

    public static int[] findRedundant(int[][] edges) {
        int n = edges.length;
        parent = new int[n + 1];
        rank = new int[n + 1];
        for (int i = 0; i <= n; i++) parent[i] = i;

        for (int[] e : edges) {
            if (!union(e[0], e[1])) return e;  // closes a cycle
        }
        return new int[0];
    }

    public static void main(String[] args) {
        int[][] edges = {{1, 2}, {1, 3}, {2, 3}};
        int[] ans = findRedundant(edges);
        System.out.println(Arrays.toString(ans));
    }
}

[2, 3]

def redundant_connection(edges):
    n = len(edges)
    parent = list(range(n + 1))   # each node is its own parent
    rank = [0] * (n + 1)          # rough height of each group

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])  # path compression
        return parent[x]

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb:
            return False                 # already connected
        if rank[ra] < rank[rb]:          # union by rank
            parent[ra] = rb
        elif rank[ra] > rank[rb]:
            parent[rb] = ra
        else:
            parent[rb] = ra
            rank[ra] += 1
        return True

    for a, b in edges:
        if not union(a, b):              # this edge closes a cycle
            return [a, b]
    return []


edges = [[1, 2], [1, 3], [2, 3]]
print(redundant_connection(edges))

[2, 3]

function redundantConnection(edges) {
  const n = edges.length;
  const parent = Array.from({ length: n + 1 }, (_, i) => i); // self parent
  const rank = new Array(n + 1).fill(0);

  function find(x) {
    if (parent[x] !== x) parent[x] = find(parent[x]); // path compression
    return parent[x];
  }

  function union(a, b) {
    const ra = find(a);
    const rb = find(b);
    if (ra === rb) return false;        // already connected
    if (rank[ra] < rank[rb]) parent[ra] = rb;       // union by rank
    else if (rank[ra] > rank[rb]) parent[rb] = ra;
    else { parent[rb] = ra; rank[ra]++; }
    return true;
  }

  for (const [a, b] of edges) {
    if (!union(a, b)) return [a, b];    // this edge closes a cycle
  }
  return [];
}

const edges = [[1, 2], [1, 3], [2, 3]];
console.log(redundantConnection(edges));

[ 2, 3 ]

Let us walk through the Python version line by line, because union-find is the part worth understanding deeply.

parent = list(range(n + 1)) sets every node as its own parent at the start. So at first every node is alone in its own group. rank = [0] * (n + 1) starts every group with rank zero, since each group is just one node.

Inside find(x), the line if parent[x] != x: checks whether x is the root. The root is the only node that is its own parent. If x is not the root, parent[x] = find(parent[x]) does two things at once. It finds the real root, and it points x straight at that root. That second part is path compression. It flattens the chain so future lookups are fast.

Inside union(a, b), we first get both roots with find. If ra == rb, the two nodes already share a root, so they are already connected. We return False, which is the signal that this edge would form a loop.

The rank lines decide which root becomes the new top. We attach the smaller-rank group under the larger-rank one. That keeps the tree short. When both ranks match, we pick one as the parent and bump its rank by one, because the tree grew slightly taller.

The main loop reads each edge in order. if not union(a, b): return [a, b] says: if the union failed, the two nodes were already connected, so this edge is the redundant one. We return it right away.

⏱️ Time and Space Complexity

The DFS approach checks connection by scanning the graph, so each edge can cost O(V). Across all edges that becomes O(V * E). Union-find is far better. With path compression and union by rank, each find or union runs in almost constant time. The exact term is the inverse Ackermann function, written as alpha of n, which stays under five for any realistic input. So processing all edges is nearly O(E). The space is O(V) for the parent and rank arrays.

🧩 Key Takeaways

• ✅ Union-find tracks which group each node is in and merges groups fast.
• ✅ The root is the top node of a group. Two nodes match when they share a root.
• ✅ Path compression points nodes straight at the root, so lookups stay short.
• ✅ Union by rank attaches the shorter group under the taller one, keeping trees flat.
• ✅ The first edge whose two nodes already share a root is the redundant one.

🚀 What’s Next?

• Number of Connected Components
• Graph Valid Tree