Leetcode:684. Redundant Connection

Posted on | Comments: | Views:
Graph Union-Find

684. Redundant Connection

题目理解:

给出一个无向边集, 返回最后出现的、使得成环的边.

思路:

将结点分类, 一开始时每个结点自成一类, 之后如果某些结点连通了, 则可以归到一类(不能连通就不是同一类)
然后遍历边集, 对边连接的两个结点归为同一类, 但是会出现以下的情况:

    1. 两个结点本来就不是同一类, 那么正常合并
    1. 两个结点本来就是同类(连通), 那么该边使得这个类成环, 记录下来这条边
      这样最后记录下来的边, 就是我们想要的答案

这里有个小问题, 如果检查同一类时使用标识(如某个数字)记录, 那么合并的时候需要遍历整个数组来检查所有标识, 总体的复杂度会上升到 $o(n^2)$ , 开销较大
所以下面的代码用并查集的数据结构来进行记录, 降低复杂度

小结:

继续找图的题目来做, 找到了这个, 一开始从DFS找回边、前进边、横跨边入手, 发现很难找到最后一条成环的边, 答案会根据边集的顺序改变…..
后来才看了下Tag, 发现是并查集, 于是换了一个思路, 也不用构造邻接链表了….
所以其实就是并查集的练手题

Submission Detail:

Detail

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<int> rooms;
    int start, end;
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        start = end = 0;
        for (int i=0; i <= edges.size(); i++) {
            rooms.push_back(i);
        }

        for (int i=0; i < edges.size(); i++) {
            if (unionset(edges[i][0], edges[i][1])) {
                start = edges[i][0];
                end = edges[i][1];
            }
        }
        
        vector<int> t;
        t.push_back(start);
        t.push_back(end);
        return t;
    }
    
    int find(int x) {
        while (x != rooms[x]) { x = rooms[x]; }
        return x;
    }

    bool unionset(int x, int y) {
        int xRoot = find(x);  
        int yRoot = find(y);  
        if (xRoot == yRoot)   
            return true;  
        rooms[xRoot] = yRoot;
        return false;
    }
};