Redundant Connection

LeetCode

第37天。

今天的题目是Redundant Connection:

这道题用并查集可以解决掉，具体思路如下：

首先初始化一个并查集，然后遍历输入edges，使用并查集查找两个节点所在的集合，如果两个节点在同一个节点中，那么往图里面加入这条边就会出现环，即无法构成树，因此这条边就是我们要求的边；如果不在集合，那么就将这条边插入到图中（即合并两个集合）。具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int root(vector<int> &ids, int i) {
    while(ids[i] != i) i = ids[i];
    return i;
}
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    if (edges.size() == 0) return vector<int>();
    vector<int> ids(edges.size());
    for(int i = 0;i < ids.size(); i++) ids[i] = i;
    
    for(auto &e: edges) {
        int n1 = root(ids, e[0]-1), n2 = root(ids, e[1]-1);
        if (n1 == n2) return e;
        ids[n1] = n2;
    }
    return *edges.rbegin();
}