3289. 서로소 집합

3289. 서로소 집합

union-find 를 이용해서 문제를 쉽게 풀 수 있었다.

같은 부모를 가지고 있으면, 1을 출력하고,

그렇지 않으면 0을 출력하면 되는 문제.

<정답 코드>

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
 
int p[1000001];
void init()
{
    for (int i = 0; i < 1000001; i++)
    {
        p[i] = i;
    }
}
 
int find(int x)
{
    if (p[x] == x)
    {
        return x;
    }
    else
    {
        return p[x] = find(p[x]);
    }
    
}
void merge(int x,int y)
{
    x = find(x);
    y = find(y);
 
    if (x == y)
    {
        return;
    }
 
    if (x < y)
    {
        swap(x, y);
    }
 
    p[y] = x;
 
    return;
 
}
int main()
{
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        init();
        int n, m;
        string ans = "";
        cin >> n >> m;
 
        for (int i = 0; i < m; i++)
        {
            int k, a, b;
            cin >> k >> a >> b;
 
            if (k == 0)
            {
                merge(a, b);
            }
            else if(k==1)
            {
                a = find(a);
                b = find(b);
 
                if (a == b)
                {
                    ans += "1";
                }
                else
                {
                    ans += "0";
                }
            }
 
        }
        
        cout << "#" << t << " " << ans << "\n";
 
    }
 
    return 0;
}