Code & Func

第37天。

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

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

1
int root(vector<int> &ids, int i) {
2
    while(ids[i] != i) i = ids[i];
3
    return i;
4
}
5
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
6
    if (edges.size() == 0) return vector<int>();
7
    vector<int> ids(edges.size());
8
    for(int i = 0;i < ids.size(); i++) ids[i] = i;
9

10
    for(auto &e: edges) {
11
        int n1 = root(ids, e[0]-1), n2 = root(ids, e[1]-1);
12
        if (n1 == n2) return e;
13
        ids[n1] = n2;
14
    }
15
    return *edges.rbegin();
1 collapsed line
16
}