LeetCode 684.冗余连接 - JavaScript

题目描述:在本问题中, 树指的是一个连通且无环的无向图

输入一个图,该图由一个有着 N 个节点 (节点值不重复 1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在 1 到 N 中间,这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ,满足 u < v,表示连接顶点 u 和 v 的无向图的边。

返回一条可以删去的边,使得结果图是一个有着 N 个节点的树。如果有多个答案,则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。

题目分析

题目很长,通俗来说就是有一棵树,然后输入中给出了这颗树中的所有节点连线,除此之外还多给了一条。这条多出来的边会导致不符合树的定义。例如在下面的例子中,多出来的[1, 4]这条边形成了环:

输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
解释: 给定的无向图为:
5 - 1 - 2
    |   |
    4 - 3

解法 1:并查集(DSU)

对一棵树来说,有着唯一的根节点。所有边[u, v]中的 u 和 v 应该都属于同一个集合,从形状上来看,它们都是连接点根节点。

如果[p, q]是重复边,那么 p 和 q 之前应该被记录到了同一集合中。所以每次在加入新边的时候,检查集合中是否已经包含边两边的节点即可。

可以使用并查集来描述这种关系,并且并查集可以快速找到节点集合以及快速合并 2 个集合。代码实现如下:

// ac地址:https://leetcode-cn.com/problems/redundant-connection/
// 原文地址:https://xxoo521.com/2020-02-28-redundant-connection/

class UnionFind {
    constructor() {
        this.parent = new Map();
    }

    // 查找元素所在集合
    find(x) {
        while (this.parent.has(x)) {
            x = this.parent.get(x);
        }
        return x;
    }

    // 合并两个集合
    union(p, q) {
        const rootP = this.find(p);
        const rootQ = this.find(q);
        if (rootP !== rootQ) {
            this.parent.set(this.find(p), this.find(q));
        }
    }
}

/**
 * @param {number[][]} edges
 * @return {number[]}
 */
var findRedundantConnection = function(edges) {
    const uf = new UnionFind();

    for (const edge of edges) {
        const p = edge[0];
        const q = edge[1];
        if (uf.find(p) === uf.find(q)) {
            return [p, q];
        }
        uf.union(p, q);
    }
    return [-1, -1];
};

解法 2: DFS

对于边[u, v]使用 DFS,检查 u、v 是否相连。如果可以,则它是重复边。

拓展思考:为什么不能使用集合(Set)?

在完成并查集的解法后,我又用了 Set 这种数据结构来尝试这题,如下所示:

/**
 * @param {number[][]} edges
 * @return {number[]}
 */
var findRedundantConnection = function(edges) {
    const set = new Set();
    for (const edge of edges) {
        if (set.has(edge[0]) && set.has(edge[1])) {
            return edge;
        }
        set.add(edge[0]).add(edge[1]);
    }
    return [-1, -1];
};

结果自然是没有 ac。错误用例是:

输入:[[3,4],[1,2],[2,4],[3,5],[2,5]]
错误输出:[2,4]

错误原因是:Set 不能保证里面的节点都属于同一个「连通分量」。例如 3、4 是连通的,1、2 是连通的,但是这是两个连通分量。

而并查集通过保存节点的 parent 指向,一直查找,最终查找到的节点可以视为这个连通分量的根节点。连通分量中的其他节点都是指向它的,因此它可以用来标识连通分量。

更多资料

若有错误,欢迎指正。若对您有帮助,请给个「关注+点赞」,您的支持是我更新的动力 👇

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×