[백준/C++] 1717 집합의 표현

1717번: 집합의 표현

대표적인 Union Find 문제 라고 합니다.

해당 알고리즘에대해서 배운적이 없었기때문에 단순히 구조체 배열 구성후

변수 a는 실행조건으로 b, c 는 단순한 구조체 배열에 속한 변수로 하여 문제를 풀려했으나 실패.

다른 풀이를 참고 하도록 합니다.

 

#include <iostream>
#define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0);
using namespace std;

// 백준 1717번 : 집합의 표현 ( Union Find 문제 )

int r[1000001]; // 제시된 최대 배열
int n, m; // 처음에 입력받을 정수 2개

int getParent(int num) { 
    if (r[num] == num) // 최상단 부모 노드 라면 반환 (함수 탈출)
        return num; 
    else {
        return r[num] = getParent(r[num]); // 없다면 재귀호출
    }
}

void join(int a, int b) { // a가 속한 곳을 b가 속한 곳으로 변경
    r[getParent(a)] = getParent(b);
}

int main()
{
    fastio;
    cin >> n >> m;

    for (int i = 0; i <= n; i++) // 0 ~ n 까지 
        r[i] = i; // r[] 을 자기 자신으로 초기화.

    while (m--)
    {
        int cmd, a, b;

        cin >> cmd >> a >> b;
        if (a == 0) // 0 이라면
            join(a, b); // a가 속한 곳을 b가 속한 곳으로 수정
        else { // 0 이아니라면 즉. 1이라면
            if (getParent(a) == getParent(b)) 
                cout << "YES\n"; // YES 출력
            else // 없다면
                cout << "NO\n"; // NO 출력 
        }
    }
    return 0;
}

Union_Find 정보 참고 블로그

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

[알고리즘] Union-Find 알고리즘 - Heee's Development Blog