[백준] 1717번 집합의 표현 (= expression of set) - 재우스 프로그래밍 (C 언어)

문제 링크 :www.acmicpc.net/problem/1717

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

#define DEBUG 1

int *inSet;

void unionSet(int, int);    //두 인자에 대해 합집합 실행
void checkSet(int, int);    //두 인자에 대해 같은 집합인지 검사
int findParent(int);        //최상위 부모를 찾아서 그 값을 return
void initSet(int);            //inSet 배열 초기화

int main(void)
{
    //집합의 개수는 n + 1개, 연산의 개수 m개
    int n = 0, m = 0;
    //연산 종류 op, 연산의 좌항 a, 연산의 우항 b
    int op = -1, a = -1, b = -1;

    scanf("%d %d", &n, &m);
    //입력 받은 크기만큼의 집합과 결과 메모리 할당
    inSet = (int *)malloc(sizeof(int) * (n + 1));

    //집합의 index와 동일한 data값을 갖고 모두 최상위 부모인 집합으로 초기화
    initSet(n);

    //m번의 명령어 실행
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &op, &a, &b);
        //a, b의 inSet에 자신의 최고 부모를 갱신한다.
        inSet[a] = findParent(a);
        inSet[b] = findParent(b);
        //합집합 실행
        if (!op)
            unionSet(a, b);
        //같은 집합인지 확인
        else
            checkSet(a, b);
    }

    free(inSet);
    return 0;
}

void unionSet(int a, int b)
{
    //합집합을 실행할 두 집합이 나뉘어져 있을 때
    if (inSet[a] != inSet[b]) {
        //a나 b 둘 중 하나의 최고 부모를 상대편의 최고 부모와 연결한다.
        inSet[inSet[a]] = inSet[b];
//or    inSet[inSet[b]] = inSet[a];
    }
    return;
}

void checkSet(int a, int b)
{
    //두 집합의 최고 부모가 같다는 것은 한 집합에 포함된다는 의미이다
    if (inSet[a] == inSet[b])
        printf("YES\n");
    else
        printf("NO\n");
    return;
}

int findParent(int cur)
{
    //저장된 최상위 부모가 자기 자신이면 return한다.
    if (cur == inSet[cur])
        return cur;
    //최상위 부모를 찾을 때까지 올라가면서 만나는 노드들을 모두 최상위 부모로 갱신해준다.
    return inSet[cur] = findParent(inSet[cur]);
}

void initSet(int n)
{
    for (int i = 0; i <= n; i++) {
        inSet[i] = i;
    }
    return;
}