LeetCode Entry

684. Redundant Connection

29.01.2025 medium 2025 kotlin rust

First edge making a cycle in graph find

684. Redundant Connection medium blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/879

Problem TLDR

First edge making a cycle in graph #medium #union_find

Intuition

Let’s add edges into a Union-Find and check for the existing connection.

Approach

  • size + 1 to simplify the code
  • path shortening is almost optimal, another optimization is ranking but not worth the keystrokes

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


    fun findRedundantConnection(g: Array<IntArray>): IntArray {
        val u = IntArray(g.size + 1) { it }
        fun f(a: Int): Int = if (a == u[a]) a else f(u[a]).also { u[a] = it }
        return g.first { (a, b) -> f(a) == f(b).also { u[u[a]] = u[b] }}
    }



    pub fn find_redundant_connection(edges: Vec<Vec<i32>>) -> Vec<i32> {
        let mut u: Vec<_> = (0..=edges.len()).collect();
        edges.into_iter().find(|e| { let (a, b) = (e[0] as usize, e[1] as usize);
            while u[a] != u[u[a]] { u[a] = u[u[a]]};
            while u[b] != u[u[b]] { u[b] = u[u[b]]};
            let r = u[a] == u[b]; let a = u[a]; u[a] = u[b]; r}).unwrap()
    }



    vector<int> findRedundantConnection(vector<vector<int>>& g) {
        int u[1001]; iota(u, u + 1001, 0);
        auto f = [&](this const auto f, int a) {
            while (u[a] != u[u[a]]) u[a] = u[u[a]]; return u[a];};
        for (auto& e: g) if (f(e[0]) == f(e[1])) return e;
            else u[u[e[0]]] = u[e[1]];
        return {};
    }