솔루션: 중복 연결

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 들었거나 유용하다고 생각되면 이 게시물에 좋아요를 누르거나 찬성 투표my solution post on Leetcode's forums를 해주세요.

Leetcode 문제 #684(중간): 중복 연결

설명:

(다음으로 이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

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]
Visual:

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

제약:

• n == edges.length
• 3 <= n <= 1000
• edges[i].length == 2
• 1 <= ai < bi <= edges.length
• ai != bi
• There are no repeated edges.
• The given graph is connected.

아이디어:

(다음으로 이동: Problem Description || 코드: JavaScript | Python | Java | C++ )

이 문제에서 중복 가장자리는 이미 연결된 그래프를 함께 연결하는 가장자리입니다. 이미 본 그래프 세그먼트가 연결되었는지 확인하기 위해 간단한 UF(union-find) 구현을 사용하여 다른 세그먼트를 추적할 수 있습니다.

UF에서는 union과 find라는 두 가지 함수를 정의해야 합니다. 찾기 기능은 노드의 혈통을 궁극적인 부모까지 재귀적으로 추적하고 부모 배열(par)의 값을 업데이트하여 다음 링크에 대한 지름길을 제공합니다.

합집합 함수는 한 세그먼트의 최종 부모를 다른 세그먼트에 할당하여 두 세그먼트를 병합합니다.

가장자리를 반복하고 가장자리의 두 정점을 찾아 동일한 세그먼트에 속하는지 확인할 수 있습니다. 그렇다면 중복 에지를 찾았고 반환할 수 있습니다. 그렇지 않은 경우 두 개의 서로 다른 세그먼트를 union으로 병합해야 합니다.

시간 복잡도: O(N) 여기서 N은 에지 길이임

공간 복잡성: par 및 재귀 스택에 대한 O(N)

자바스크립트 코드:

(다음으로 이동: Problem Description || Solution Idea )

var findRedundantConnection = function(edges) {
    let par = Array.from({length: edges.length + 1}, (_,i) => i)
    const find = x => x === par[x] ? par[x] : par[x] = find(par[x])
    const union = (x,y) => par[find(y)] = find(x)
    for (let [a,b] of edges)
        if (find(a) === find(b)) return [a,b]
        else union(a,b)
};

파이썬 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        par = [i for i in range(len(edges) + 1)]
        def find(x: int) -> int:
            if x != par[x]: par[x] = find(par[x])
            return par[x]
        def union(x: int, y: int) -> None:
            par[find(y)] = find(x)
        for a,b in edges:
            if find(a) == find(b): return [a,b]
            else: union(a,b)

자바 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        par = new int[edges.length+1];
        for (int i = 0; i < par.length; i++)
            par[i] = i;
        for (int[] e : edges)
            if (find(e[0]) == find(e[1])) return e;
            else union(e[0],e[1]);
        return edges[0];
    }
    private int[] par;
    private int find(int x) {
        if (x != par[x]) par[x] = find(par[x]);
        return par[x];
    }
    private void union(int x, int y) {
        par[find(y)] = find(x);
    }
}

C++ 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        par.resize(edges.size()+1);
        for (int i = 0; i < par.size(); i++)
            par[i] = i;
        for (auto& e : edges)
            if (find(e[0]) == find(e[1])) return e;
            else uniun(e[0],e[1]);
        return edges[0];
    }
private:
    vector<int> par;
    int find(int x) {
        if (x != par[x]) par[x] = find(par[x]);
        return par[x];
    }
    void uniun(int x, int y) {
        par[find(y)] = find(x);
    }
};