2021.03.07

问题：无向图里找环
解：使用并查集(简单一点)
每一条边 = 合并两个集合，如果两个点在一个集合里，那么加完一条边后，会形成一个环。circle
然后在枚举边时，从前往后枚举，这样最后一个出现环的位置的边(封口的位置)，就是最后环出现的边。
并查集操作 TS: $O(1)$

class Solution {
public:
    vector<int> p; //并查集
    int find(int x){
        //并查集核心：找根节点(祖宗) (和路径压缩)
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size(); //总边数 = 总点数
        p.resize(n + 1); //初始化p的大小
        for (int i = 1; i <= n; i++) p[i] = i; //初始化并查集大小。

        for (auto& e : edges){ // 从前往后枚举所有边
            int a = find(e[0]), b = find(e[1]); //a是第一个点的根节点，b是第二个点的根节点
            if (a != b) p[a] = b; //说明没有出现环a≠b // 合并a和b即可
            else return e; //否则当前边就是最后出现的边
        }
        return {}; //这里不会执行

    }
};

2020.09 当初啥都不懂。纯吹水(虽然现在也不是彻底掌握)

题目描述

Follow Up Qs: 第二题链接

算法1

(并查集) $O(N)$ 因为 $O(\alpha(N)))$ 大约是$O(1)$

blablabla

C++ 代码

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        vector<int> rp(1001);
        int sz = edges.size();
        // 初始化各元素为单独的集合，代表节点就是其本身
        for(int i=0;i<sz;i++)
            rp[i] = i;
        for(int j=0;j<sz;j++){
            // 找到边上两个节点所在集合的代表节点
            int set1 = find(edges[j][0], rp);
            int set2 = find(edges[j][1], rp);
            if(set1 == set2)  // 两个集合代表节点相同，说明出现环，返回答案
                return edges[j]; 
            else    // 两个集合独立，合并集合。将前一个集合代表节点戳到后一个集合代表节点上
                rp[set1] = set2;
        }
        return {0, 0};
    }

    // 查找路径并返回代表节点，实际上就是给定当前节点，返回该节点所在集合的代表节点
    // 之前这里写的压缩路径，引起歧义，因为结果没更新到vector里，所以这里改成路径查找比较合适
    // 感谢各位老哥的提议
    int find(int n, vector<int> &rp){
        int num = n;
        while(rp[num] != num)
            num = rp[num];
        return num;
    }
};

算法2

(并查集) $O(N)$

时间复杂度

参考文献

Python 代码

def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        vector = [i for i in range(len(edges) + 1)]
        def find_origin(num):
            n = num
            while vector[n] != n:n = vector[n]
            return n
        for info in edges:
            o1 = find_origin(info[0])
            o2 = find_origin(info[1])
            if o1 == o2:return info
            vector[o1] = vector[o2]