684. Redundant Connection

Hint

class UnionFind {
private:
    // To store the parent of each node
    // To store the rank (or size) of each tree

public:
    // Constructor to initialize UnionFind structure
    UnionFind()
    {
        // +1 because nodes are 1-indexed
        // +1 for the same reason
        for ()
        {
            // Each node is its own parent initially
            // Initial rank of each node is 1
        }
    }

    // Find the representative (or root) of the set containing 'x'
    int find()
    {
        if()
        {
            // Path compression: flatten the tree
        }
    }

    // Union the sets containing 'n1' and 'n2'
    void unionFind()
    {
        // Find root of the set containing 'n1'
        // Find root of the set containing 'n2'

        // 'n1' and 'n2' are already in the same set

        // Union by rank: attach the smaller tree under the root of the larger tree
        if()
        {
            // Attach 'p2' to 'p1'
            // Increase the rank of 'p1'
        }
        else
        {
            // Attach 'p1' to 'p2'
            // Increase the rank of 'p2'
        }
    }
};

class Solution {
public:
    // Find the redundant connection in the graph represented by 'edges'
    vector<int> findRedundantConnection(vector<vector<int>>& edges)
    {
        // Initialize UnionFind for 'n' nodes

        for ()
        {
            // Check if the nodes 'edge[0]' and 'edge[1]' are in the same set
            if ()
            {
                // This edge is redundant
            }
            // Union the sets containing 'edge[0]' and 'edge[1]'
        }
        // In case no redundant edge is found, though there should be one
    }
};

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;
public:
    UnionFind(int n)
    {
        parent.resize(n + 1);
        rank.resize(n + 1);
        for (int i = 0; i <= n; ++i)
        {
            parent[i] = i;
            rank[i] = 1;
        }
    }

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

    void unionFind(int n1, int n2)
    {
        int p1 = find(n1);
        int p2 = find(n2);

        if(p1 == p2) return;

        if(rank[p1] > rank[p2])
        {
            parent[p2] = p1;
            rank[p1] += rank[p2];
        }
        else
        {
            parent[p1] = p2;
            rank[p2] += rank[p1];
        }
    }
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges)
    {
        int n = edges.size();
        UnionFind uf(n);
        for (const auto& edge : edges)
        {
            if (uf.find(edge[0]) == uf.find(edge[1]))
            {
                return edge;
            }
            uf.unionFind(edge[0], edge[1]);
        }
        return {};
    }
};

• T: $O(N)$
• S: $O(N)$