[LeetCode] 684. Redundant Connection

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

leetcode - Redundant Connection

문제 유형: 유니온-파인드, 분리 집합

문제 난이도: Medium

 

문제

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.

 

사이클을 일으키는 간선을 찾아 반환하시오. 유사답안 중에서는 가장 늦게 나오는 간선으로 하시오.

 

풀이

유니온 파인드를 하면서 병합 과정에서 병합에 실패(이미 같은 집합)라면 그 간선을 반환한다.

 

코드

C++

class Solution {
public:
    int getRoot(int x, vector<int>& parent) {
        if(parent[x] == x) return x;
        return parent[x] = getRoot(parent[x], parent);
    }
    bool merge(int x, int y, vector<int>& parent) {
        int rootX = getRoot(x, parent);
        int rootY = getRoot(y, parent);

        if(rootX == rootY) return false;

        if(rootX < rootY) {
            parent[rootY] = rootX;
        } else {
            parent[rootX] = rootY;
        }

        return true;
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int> parent(n+1);
        iota(parent.begin(), parent.end(), 0);

        for(const auto &edge : edges) {
            int u = edge[0];
            int v = edge[1];

            if(!merge(u, v, parent)) return {u, v};
        }

        return {-1, -1};
    }
};