1717번

1717번 - 집합의 표현

union- find 를 통해서 문제를 해결했다.

union을 할 때는 경로의 압축을 해주는 것이 시간초과를 해결하는데 주요했다.

그리고 이 문제의 경우, 입력,출력이 많기 떄문에 cin, cout 대신 printf,scanf 를 써줘야 했다.

<정답 코드>

#include<iostream>
#include<vector>
 
using namespace std;
int n, m;
vector<int> p;
 
int find(int x)
{
    if (x == p[x])
    {
        return x;
    }
 
    return p[x] = find(p[x]);
}
 
void merge(int x, int y)
{
    int px = find(x);
    int py = find(y);
    if (px == py)
    {
        return;
    }
 
    p[py] = px;
    return;
    
}
 
 
int main()
{
 
    scanf("%d %d", &n, &m);
    p.resize(n + 1);
 
    for (int i = 0; i <= n; i++)
    {
        p[i] = i;
    }
 
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
 
        if (a == 0)
        {
            merge(b, c);
        }
        else if (a == 1)
        {
            int x = find(b);
            int y = find(c);
 
            if (x == y)
            {
                printf("YES\n");
            }
            else
            {
                printf("NO\n");
            }
        }
    }
 
    return 0;
}