684. 冗余连接

Problem: 684. 冗余连接

Reference

代码随想录 (programmercarl.com)

思路

本题使用并查集，不要忘记对father数组进行初始化。

如果两个边上的节点已经一个集合里面了说明他们是多余的边。

如下图

解题方法

描述你的解题方法

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

class Solution {
public:
    int n = 1005;
    vector<int> father = vector<int>(n, 0);
    void init() {
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
    }
    int find(int u) {
        if (u == father[u]) {
            return u;
        }
        return father[u] = find(father[u]);
    }
    bool isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }
    void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v)
            return;
        father[v] = u;
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        init();
        for (int i = 0; i < edges.size(); i++) {
            if (isSame(edges[i][0], edges[i][1]))
                return edges[i];
            else
                join(edges[i][0], edges[i][1]);
        }
        return {};
    }
};