본문 바로가기

백준

1717 집합의 표현

 

union find 연습문제로 풀었던 거

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> parent;

void    init(int n)
{
    parent.resize(n + 1);

    for (int i = 0; i <= n; i++)
        parent[i] = i;
}

int     find(int x)
{
    if (x == parent[x])
        return x;
    return (parent[x] = find(parent[x]));
}

void    merge(int x, int y)
{
    x = find(x);
    y = find(y);
    
    parent[x] = y;
}

int     main()
{
    int n, m;

    scanf("%d %d", &n, &m);
    init(n);
    for (int i = 0; i < m; i++)
    {
        int num, a, b;
        scanf("%d %d %d", &num, &a, &b);
        if (num == 0)
        {
            merge(a, b);
        }
        else
        {
            if (find(a) == find(b))
                printf("YES\n");
            else
                printf("NO\n");
        }
    }
    
    return (0);
}

'백준' 카테고리의 다른 글

1260 DFS와 BFS  (0) 2020.07.18
15809 전국시대  (0) 2020.03.15
2239 스도쿠  (0) 2020.02.24
2447 별 찍기 - 10  (0) 2020.02.20
15652 N과 M (4)  (0) 2020.02.19