[LeetCode][Union-Find] Redundant Connection 풀어보기

https://leetcode.com/problems/redundant-connection/description/?utm_source=chatgpt.com

Redundant Connection - LeetCode

 

Union-Find를 통해서 Cycle을 찾아내는 문제입니다.

 

처음에는 문제가 사이클을 끊어낼 수 있는 가장 큰 수의 간선이라고 생각했는데, 다시보니

 

주어진 간선 순서에 따라 간선을 이어가며, 사이클이 만들어지는 마지막 간선을 찾는 것이었습니다.

따라서 cycle을 찾는 간단한 방법 중 하나인 union-find를 사용했습니다.

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();

        parent.resize(n + 1);
        size.resize(n + 1, 1);

        vector<int> answer(2);

        for (int i = 0; i <= n; ++i)
        {
            parent[i] = i;
        }

        for (auto edge : edges)
        {
            int a = edge[0];
            int b = edge[1];

            if (!unite(a, b))
            {
                answer[0] = a;
                answer[1] = b;
                break;
            }
        }

        return edges[0];

    }

    int find(int a)
    {
        if (a == parent[a])
            return a;
        
        return parent[a] = find(parent[a]);
    }

    bool unite(int a, int b)
    {
        int rootA = find(a);
        int rootB = find(b);

        if (rootA == rootB)
            return false;

        if (size[rootA] < size[rootB])
        {
            swap(rootA, rootB);
        }

        parent[rootB] = rootA;
        size[rootA] += size[rootB];

        return true;
    }
public:
    vector<int> parent;
    vector<int> size;
};

 

c++에서는 union이 예약 키워드이기 때문에 이를 위해 다른 이름을 사용했습니다.