[ SWEA 3289 ] 서로소 집합 (C++)

SWExpertAcademy의 서로소집합(3289) 문제이다.

[ 문제풀이 ]

1) 본인은 이 문제를 크루스칼 알고리즘을 적용시켜서 구현해 보았다.

    먼저 크루스칼 알고리즘에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

    [ 크루스칼 알고리즘 알아보기(Click) ]

    그렇다면 이 문제에서 크루스칼을 어떻게 적용시킬까?? 위의 글을 읽고왔다면 알겠지만 크루스칼 알고리즘은 '부모가 서로

    같은 노드인지 확인하고, 같다면 서로 하나가 되도록 연결시켜주는 방법' 을 이용한다.

    이 부분을 이용해서 문제에 적용시켜 보았다.

    각각의 집합을 합치라는 연산이 나올 때 마다 같은 부모를 갖는지 확인 후, 합쳐주는 연산을 해 주었다.

    이 후, 같은 집합에 포함되어있는지 판단하는 명령이 나올 때 마다 같은 부모를 갖는지만 확인해 주었다.

   

[ 소스코드 ] 

#include<iostream>
#include<vector>
#include<cstring>
 
#define endl "\n"
#define MAX 1000000 + 1
using namespace std;
 
int N, M;
int Parent[MAX];
vector<int> Answer;
 
void Initialize()
{
    for (int i = 1; i < MAX; i++)
    {
        Parent[i] = i;
    }
    Answer.clear();
}
 
int Find(int x)
{
    if (Parent[x] == x) return x;
    else return Parent[x] = Find(Parent[x]);
}
 
void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);
    if (x != y)
    {
        Parent[y] = x;
    }
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        if (a == 0)
        {
            Union(b, c);
        }
        else
        {
            b = Find(b);
            c = Find(c);
 
            if (b == c) Answer.push_back(1);
            else Answer.push_back(0);
        }
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
 
        cout << "#" << T << " ";
        for (int i = 0; i < Answer.size(); i++)
        {
            cout << Answer[i];
        }
        cout << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}