Redundant Connection

NeetCode: Redundant Connection · LeetCode: 684. Redundant Connection · Difficulty: Medium

A tree with n nodes labeled 1..n had one extra edge added, so the graph now has n edges and exactly one cycle. Return an edge that can be removed to make it a tree again. If there are several answers, return the one that appears last in the input.

Example

Text

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

Add the edges in input order. The first edge whose two endpoints are already connected closes the cycle. Since the graph has exactly one cycle, that edge is the last cycle edge in the input, which is the required answer.

Brute force: search for a path before adding each edge

Keep an adjacency list of the edges accepted so far. Before adding [a, b], run a DFS to test whether b is already reachable from a. If it is, the edge is redundant. The adjacency list is a List<List<Integer>> indexed by node label, with one unused slot at index 0. The method returns an empty array when no edge closes a cycle, which cannot happen for valid input.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

class Solution {
    private boolean connected(List<List<Integer>> adj, int a, int b) {
        boolean[] visited = new boolean[adj.size()];
        visited[a] = true;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(a);
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (node == b) {
                return true;
            }
            for (int next : adj.get(node)) {
                if (!visited[next]) {
                    visited[next] = true;
                    stack.push(next);
                }
            }
        }
        return false;
    }

    public int[] findRedundantConnection(int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= edges.length; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            if (connected(adj, e[0], e[1])) {
                return e;
            }
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        return new int[0];
    }
}

public class Main {
    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}})));
        int[][] edges = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}};
        System.out.println(Arrays.toString(s.findRedundantConnection(edges)));
        System.out.println(Arrays.toString(s.findRedundantConnection(new int[][]{{1, 2}, {2, 1}})));
    }
}

Output

[2, 3]
[1, 4]
[2, 1]

Time: O(n^2), one O(n) search per edge. Space: O(n).

Optimal: union-find (disjoint set union)

The question "are a and b already connected?" is exactly what union-find answers in near-constant time. Each node starts as its own set. For an edge, find the root of both endpoints: equal roots mean the edge closes a cycle; different roots mean the two sets are merged. Path compression (halving) and union by size make each operation O(alpha(n)), where alpha is the inverse Ackermann function and is at most 4 for any realistic input.

The sets live in two int arrays: parent (each node's parent, a root points to itself) and size (the size of the set for each root).

Java

import java.util.Arrays;

class Dsu {
    private final int[] parent;
    private final int[] size;

    Dsu(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

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

    /** Returns false if a and b were already in the same set. */
    boolean union(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra == rb) {
            return false;
        }
        if (size[ra] < size[rb]) {
            int tmp = ra;
            ra = rb;
            rb = tmp;
        }
        parent[rb] = ra;
        size[ra] += size[rb];
        return true;
    }
}

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        Dsu dsu = new Dsu(edges.length + 1);
        for (int[] e : edges) {
            if (!dsu.union(e[0], e[1])) {
                return e;
            }
        }
        return new int[0];
    }
}

public class Main {
    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}})));
        int[][] edges = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}};
        System.out.println(Arrays.toString(s.findRedundantConnection(edges)));
        System.out.println(Arrays.toString(s.findRedundantConnection(new int[][]{{1, 2}, {2, 1}})));
    }
}

Output

[2, 3]
[1, 4]
[2, 1]

Time: O(n * alpha(n)), effectively linear. Space: O(n).