力扣684、冗余连接

吐槽：题目说了一句，如果有多个答案，则返回数组 edges 中最后出现的边，tmmd 力扣题解他是从前往后进行的，构成回路就return了。

题目

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。

题解

• 按秩合并的并查集
• 从前往后加边，并判断是否构成联通图

class Solution {
public:
    #define maxn 1024
    #define swap(a, b) \
        (a) ^= (b), (b) ^= (a), (a) ^= (b)

    int father[maxn];
    int size[maxn];

    int find(const int& a) { return a != father[a] ? father[a] = find(father[a]) : a; }
    int merge(const int& a, const int& b) {
        int fa = find(a), fb = find(b);
        if (fa == fb) return 1;
        if (size[fa] < size[fb]) swap(fa, fb);
        father[fb] = fa;
        size[fa] += size[fb];
        return 0;
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        for (int i = 1; i < maxn; ++i) {
            father[i] = i;
            size[i] = 1;
        }
        for (int i = 0; i < edges.size(); ++i) {
            int a = edges[i][0], b = edges[i][1];
            if (merge(a, b) == 1) return edges[i];
        }
        return edges[0];
    }
};

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/redundant-connection