Redundant Connection

Leetcode Problem 684: Redundant Connection

Problem Summary

You are given a graph that started as a tree with n nodes labeled from 1 to n, and then one additional edge was added. The graph is represented as an array of edges where each edge connects two different vertices. Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple valid answers, return the edge that occurs last in the input. The number of edges is between 3 and 1,000, and there are no repeated edges.

Techniques

• Depth-First Search
• Breadth-First Search
• Union-Find
• Graph Theory

Solution

import { UnionFind } from "../union-find"

function findRedundantConnection(edges: number[][]): number[] {
    const n = edges.length
    const uf = new UnionFind(n + 1)

    for (const edge of edges) {
        const [u, v] = edge
        if (uf.find(u) === uf.find(v)) {
            return edge
        } else {
            uf.union(u, v)
        }
    }

    return [-1, -1]
}

console.log(findRedundantConnection([[1,2],[2,3],[3,4],[1,4],[1,5]]))