Redundant Connection

class Solution {
    vector<int> parent, rnk;
    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (rnk[a] < rnk[b]) swap(a, b);
        parent[b] = a;
        if (rnk[a] == rnk[b]) ++rnk[a];
        return true;
    }
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        parent.resize(n + 1); rnk.assign(n + 1, 0);
        iota(parent.begin(), parent.end(), 0);
        for (auto& e : edges) {
            if (!unite(e[0], e[1])) return e;
        }
        return {};
    }
};

func findRedundantConnection(edges [][]int) []int {
    n := len(edges)
    parent := make([]int, n+1)
    rnk := make([]int, n+1)
    for i := range parent {
        parent[i] = i
    }
    var find func(x int) int
    find = func(x int) int {
        for parent[x] != x {
            parent[x] = parent[parent[x]]
            x = parent[x]
        }
        return x
    }
    unite := func(a, b int) bool {
        a, b = find(a), find(b)
        if a == b {
            return false
        }
        if rnk[a] < rnk[b] {
            a, b = b, a
        }
        parent[b] = a
        if rnk[a] == rnk[b] {
            rnk[a]++
        }
        return true
    }
    for _, e := range edges {
        if !unite(e[0], e[1]) {
            return e
        }
    }
    return nil
}

from typing import List

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        parent = list(range(n + 1))
        rnk = [0] * (n + 1)

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def unite(a: int, b: int) -> bool:
            a, b = find(a), find(b)
            if a == b:
                return False
            if rnk[a] < rnk[b]:
                a, b = b, a
            parent[b] = a
            if rnk[a] == rnk[b]:
                rnk[a] += 1
            return True

        for e in edges:
            if not unite(e[0], e[1]):
                return e
        return []

function findRedundantConnection(edges) {
    const n = edges.length;
    const parent = new Array(n + 1);
    const rnk = new Array(n + 1).fill(0);
    for (let i = 0; i <= n; i++) parent[i] = i;
    const find = (x) => {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    const unite = (a, b) => {
        a = find(a); b = find(b);
        if (a === b) return false;
        if (rnk[a] < rnk[b]) [a, b] = [b, a];
        parent[b] = a;
        if (rnk[a] === rnk[b]) rnk[a]++;
        return true;
    };
    for (const e of edges) {
        if (!unite(e[0], e[1])) return e;
    }
    return [];
}

class Solution {
    private int[] parent;
    private int[] rnk;

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        parent = new int[n + 1];
        rnk = new int[n + 1];
        for (int i = 0; i <= n; i++) parent[i] = i;
        for (int[] e : edges) {
            if (!unite(e[0], e[1])) return e;
        }
        return new int[0];
    }

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

    private boolean unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (rnk[a] < rnk[b]) { int t = a; a = b; b = t; }
        parent[b] = a;
        if (rnk[a] == rnk[b]) rnk[a]++;
        return true;
    }
}

function findRedundantConnection(edges: number[][]): number[] {
    const n = edges.length;
    const parent: number[] = new Array<number>(n + 1);
    const rnk: number[] = new Array<number>(n + 1).fill(0);
    for (let i = 0; i <= n; i++) parent[i] = i;
    const find = (x: number): number => {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    const unite = (a: number, b: number): boolean => {
        a = find(a); b = find(b);
        if (a === b) return false;
        if (rnk[a] < rnk[b]) [a, b] = [b, a];
        parent[b] = a;
        if (rnk[a] === rnk[b]) rnk[a]++;
        return true;
    };
    for (const e of edges) {
        if (!unite(e[0], e[1])) return e;
    }
    return [];
}