684. Redundant Connection

Leetcode

https://leetcode.com/problems/redundant-connection/description/

題目

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Example 1:

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

Example 2:

Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]

前置知識 - Union-Find 算法

fucking-algorithm/算法思维系列/UnionFind算法详解.md at master · labuladong/fucking-algorithmGitHub

說明

題目給出的是一個環形相連的樹狀結構，edges 代表著相連的邊界，但其中會有一條邊界刪掉後就可以避免樹狀結構環形相連

範例：edges = [[1,2],[1,3],[2,3]]

最後 [2, 3] 節點連在一起的話，會導致整體結構變環形，因此需要刪掉的就是最後一條會導致環形的 [2, 3] edge

解答

• 方法一 - Union find

var findRedundantConnection = function (edges) {
    const parent = Array.from({ length: edges.length + 1 })
        .map((_, index) => index)

    function find(index) {
        while (index !== parent[index]) {
            index = parent[index];
        }
        return index
    }

    function union(u, v) {
        let rootU = find(u);
        let rootV = find(v);
        if (rootU === rootV) {
            return true;
        }
        parent[rootU] = rootV;
    }

    for (let edge of edges) {
        const [u, v] = edge;
        const isUnion = union(u, v)
        if (isUnion) return [u, v];
    }

    return []
};

參考資料

LeetCode 684. Redundant Connection — JavaScriptMedium