백준 1717번 집합의 표현

문제 링크입니다: https://www.acmicpc.net/problem/1717

카카오 Code Festival 예선에서 Union Find(=Disjoint Set) 자료구조를 사용하는 문제들에서 막혔기 때문에 풀어봤던 문제였습니다.

알고리즘은 아래와 같습니다.

1. 초기에는 0~N까지의 집합의 부모는 자기 자신입니다.(-1로 표현)

2. 0이 입력되면 합치는 연산입니다.

i) 같은 원소에 대해 합치거나, 부모가 동일한 원소를 합칠 필요가 없습니다.

ii) 집합의 크기가 큰 쪽에 작은 쪽을 합쳐줍니다.

->여기서 집합의 크기는 abs(arr[parent]) 즉, 부모 인덱스에 있는 값의 절대값으로 표현합니다.

3. 1이 입력되면 탐색하는 연산입니다.

i) 같은 원소이거나, 부모가 동일한 원소이면 같은 집합 내에 있습니다.

ii) 부모가 동일하지 않다면 다른 집합입니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 1000000 + 1;

 

int N, M;

int arr[MAX];

 

//부모 찾는 연산

int findParent(int num)

{

        if (arr[num] < 0)

                 return num;

 

        int parent = findParent(arr[num]);

        arr[num] = parent;

        return parent;

}

 

void merge(int aParent, int bParent)

{

        //집합의 크기가 더 큰 쪽으로 합쳐진다

        if (abs(aParent) >= abs(bParent))

        {

                 arr[aParent] += arr[bParent];

                 arr[bParent] = aParent;

        }

        else

        {

                 arr[bParent] += arr[aParent];

                 arr[aParent] = bParent;

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N >> M;

 

        for (int i = 0; i <= N; i++)

                 arr[i] = -1;

 

        for (int i = 0; i < M; i++)

        {

                 int op, a, b;

                 cin >> op >> a >> b;

 

                 if (op == 0)

                 {

                         if (a == b)

                                 continue;

 

                         int aParent = findParent(a);

                         int bParent = findParent(b);

                         if (aParent == bParent)

                                 continue;

 

                         merge(aParent, bParent);

                 }

                 else

                 {

                         if (a == b)

                         {

                                 cout << "YES\n";

                                 continue;

                         }

 

                         int aParent = findParent(a);

                         int bParent = findParent(b);

                         if (aParent == bParent)

                                 cout << "YES\n";

                         else

                                 cout << "NO\n";

                 }

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~