4. Redundant Connection

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Example 1:

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

Example 2:

Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]

Solution: (Union find)

class Solution
{
public:
    int findPar(vector<int> &v, int node)
    {
        if (v[node] == -1)
        {
            return node;
        }

        v[node] = findPar(v, v[node]);
        return v[node];
    }

    void uni(vector<int> &v, vector<int> &rank, int parA, int parB)
    {
        if (parA != parB)
        {

            if (rank[parA] > rank[parB])
            {
                v[parB] = parA;
            }
            else if (rank[parB] > rank[parA])
            {
                v[parA] = parB;
            }
            else
            {
                v[parA] = parB;
                rank[parB]++;
            }
        }

        return;
    }

    vector<int> findRedundantConnection(vector<vector<int>> &edges)
    {
        int n = edges.size();

        vector<int> res(2);

        vector<int> v(n + 1, -1);
        vector<int> rank(n + 1, 0);

        for (int i = 0; i < edges.size(); i++)
        {
            int a = edges[i][0];
            int b = edges[i][1];

            int parA = findPar(v, a);
            int parB = findPar(v, b);

            if (parA != parB)
            {
                uni(v, rank, parA, parB);
            }
            else
            {
                res[0] = a;
                res[1] = b;
            }
        }

        return res;
    }
};