LeetCode-684. 冗余连接

淩亂°似流年 2022-03-08 10:30 148阅读 0赞

# [684. 冗余连接][684.] #

返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 \[u, v\] 应满足相同的格式 u < v。

示例 1：

输入: [[1,2], [1,3], [2,3]]
    输出: [2,3]
    解释: 给定的无向图为:
      1
     / \
    2 - 3

示例 2：

输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
    输出: [1,4]
    解释: 给定的无向图为:
    5 - 1 - 2
        |   |
        4 - 3

注意:

*  输入的二维数组大小在 3 到 1000。
 *  二维数组中的整数在1到N之间，其中N是输入数组的大小。

### 并查集 树 图 ###

把相连的结点连到一个根节点上，当最后加入的结点的根节点相同时，则说明此边将构成一个环，所以就去掉这条边，也就是要删掉的边。

class Solution { 
    public:
        int findroot(int x,vector<int> &p) //查找根结点
        { 
            if(x == p[x]) return x;
            return p[x]=findroot(p[x],p);
        }
        void merge(int x,int y,vector<int> &arr,vector<int> &p) //路径压缩
        { 
            int dx = findroot(x,p);
            int dy = findroot(y,p);
            if(dx == dy)  //如果两个的根节点相同，说明加上这条边构成一个环，顾要删掉这条边
            { 
                arr[0] = x;
                arr[1] = y;
                return;
            }
            p[dy] = dx;
        }
        vector<int> findRedundantConnection(vector<vector<int>>& edges) { 
            vector<int> p(edges.size()+1);
            vector<int> arr(2); //存储要删除的两结点之间的边
            for(int i=1;i<=edges.size();i++) //初始化
                p[i]=i;
            for(auto r:edges)
            { 
                merge(r[0],r[1],arr,p); //连接两个结点
            }
            return arr;
        }
    };

[684.]: https://leetcode-cn.com/problems/redundant-connection/submissions/