Code & Fun

第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();
}

本文首发于Code & Fun