[C] 백준 1717번: 집합의 표현

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

#include <stdio.h>
#include <stdlib.h>

int *parents;

int findParent(int x)
{
    if (parents[x] == x)
        return x;

    parents[x] = findParent(parents[x]);
    return parents[x];
}

void unionSets(int x, int y)
{
    int parentX = findParent(x);
    int parentY = findParent(y);

    if (parentX < parentY)
        parents[parentX] = parentY;
    else
        parents[parentY] = parentX;
}

int main()
{
    int i;

    int n, m;
    scanf("%d %d", &n, &m);

    // parents 초기화
    parents = malloc(sizeof(int) * (n + 1));

    for (i = 1; i < n + 1; i++)
        parents[i] = i;

    // 연산 수행
    int order, a, b;
    int parentA, parentB;
    for (i = 0; i < m; i++)
    {
        scanf("%d %d %d", &order, &a, &b);

        if (order == 0)
            unionSets(a, b);
        else if (order == 1)
        {
            parentA = findParent(a);
            parentB = findParent(b);

            if (parentA == parentB)
                printf("YES\n");
            else
                printf("NO\n");
        }
    }

    return 0;
}

유니온 파인드만 알고 있다면 매우 쉬운 문제이다. 0에 대한 연산은 단순히 union()만 수행하면 된다. 1에 대한 연산은, a와 b에 대한 findParent()를 수행하고 이 둘의 값을 비교하여 같은 집합에 속해있는지를 확인하면 된다.