??Blog ：《LeetCode 684.冗余連接 - JavaScript》

題目描述：在本問題中, 樹指的是一個連通且無環(huán)的無向圖。

輸入一個圖，該圖由一個有著 N 個節(jié)點 (節(jié)點值不重復 1, 2, ..., N) 的樹及一條附加的邊構(gòu)成。附加的邊的兩個頂點包含在 1 到 N 中間，這條附加的邊不屬于樹中已存在的邊。

結(jié)果圖是一個以邊組成的二維數(shù)組。每一個邊的元素是一對[u, v] ，滿足 u < v，表示連接頂點 u 和 v 的無向圖的邊。

返回一條可以刪去的邊，使得結(jié)果圖是一個有著 N 個節(jié)點的樹。如果有多個答案，則返回二維數(shù)組中最后出現(xiàn)的邊。答案邊 [u, v] 應滿足相同的格式 u < v。

題目分析

題目很長，通俗來說就是有一棵樹，然后輸入中給出了這顆樹中的所有節(jié)點連線，除此之外還多給了一條。這條多出來的邊會導致不符合樹的定義。例如在下面的例子中，多出來的[1, 4]這條邊形成了環(huán)：

輸入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
輸出: [1,4]
解釋: 給定的無向圖為:
5 - 1 - 2
    |   |
    4 - 3

解法 1：并查集（DSU）

對一棵樹來說，有著唯一的根節(jié)點。所有邊[u, v]中的 u 和 v 應該都屬于同一個集合，從形狀上來看，它們都是連接點根節(jié)點。

如果[p, q]是重復邊，那么 p 和 q 之前應該被記錄到了同一集合中。所以每次在加入新邊的時候，檢查集合中是否已經(jīng)包含邊兩邊的節(jié)點即可。

可以使用并查集來描述這種關(guān)系，并且并查集可以快速找到節(jié)點集合以及快速合并 2 個集合。代碼實現(xiàn)如下：

// 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 這種數(shù)據(jù)結(jié)構(gòu)來嘗試這題，如下所示：

/**
 * @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];
};

結(jié)果自然是沒有 ac。錯誤用例是：

輸入：[[3,4],[1,2],[2,4],[3,5],[2,5]]
錯誤輸出：[2,4]

錯誤原因是：Set 不能保證里面的節(jié)點都屬于同一個「連通分量」。例如 3、4 是連通的，1、2 是連通的，但是這是兩個連通分量。

而并查集通過保存節(jié)點的 parent 指向，一直查找，最終查找到的節(jié)點可以視為這個連通分量的根節(jié)點。連通分量中的其他節(jié)點都是指向它的，因此它可以用來標識連通分量。

更多資料

若有錯誤，歡迎指正。若對您有幫助，請給個「關(guān)注+點贊」，您的支持是我更新的動力 ??

• ??Blog：劍指 Offer + Leetcode 題解
• ??Github ：https://github.com/dongyuanxin/blog
• ?? 公眾號：心譚博客