Time Cost

15min1s

Implementation

Disjoint Set Union to find the redundant connection.

Code

• Solution ```c++ class Solution { vector parent; vector rank;

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

  void join(int u, int v) { int rootU = find(u), rootV = find(v); if (rootU != rootV) { // Union by rank to balance trees if (rank[rootU] > rank[rootV]) parent[rootV] = rootU; else if (rank[rootU] < rank[rootV]) parent[rootU] = rootV; else { parent[rootV] = rootU; rank[rootU]++; } } }

public: vector findRedundantConnection(vector<vector>& edges) { int n = edges.size(); parent.resize(n + 1); rank.resize(n + 1, 0);

    // Initialize each node as its own parent
    for (int i = 1; i <= n; i++) parent[i] = i;

    for (auto& edge : edges) {
        int u = edge[0], v = edge[1];
        if (find(u) == find(v)) return edge; // Cycle detected!
        join(u, v); // Merge sets
    }
    
    return {}; // Unreachable for valid inputs
} }; ```