1、思路

• 一棵有n个节点的树有n - 1条边，若再加一条边，则树内必成环，题目要求我们找出这条使得树成环的边；

• 构造并查集，遍历所有的边，每条边分两种情况讨论：

  1、若一条边的两节点分别属于两个不同的子图，添加一条边连接这两个节点，会将它们所在的子图连在一起，但不会形成环；

  2、若两节点属于同一子图，添加一条边就会形成环。

2、代码

class Solution {
public:
    int findFather(vector<int>& fathers, int i)         //找根节点
    {
        if (fathers[i] != i)
        {
            return findFather(fathers, fathers[i]);
        }

        return i;
    }

    bool isUnion(vector<int>& fathers, int i, int j)    //判断两点是否在同一个子集中
    {
        int fatherOfI = findFather(fathers, i);
        int fatherOfJ = findFather(fathers, j);

        if (fatherOfI != fatherOfJ)
        {
            fathers[fatherOfI] = fatherOfJ;
            return true;
        }

        return false;
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        vector<int> fathers(1001);                      // n 最多为1000
        for (int i = 0; i < edges.size(); ++ i)         //并查集初始化
        {
            fathers[i] = i;
        }

        for (auto& edge : edges)
        {
            //若两点已在同一个子集内，则这条边会导致环
            if (!isUnion(fathers, edge[0], edge[1]))
            {
                return edge;
            }
        }

        return {};
    }
};