[백준] 6018번 Tea Time

문제 출처: https://www.acmicpc.net/problem/6018

6018번: Tea Time

유니온 파인드를 이용하여 같은 집합인지 확인하여 출력한다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

int arr[1001];

int find(int n) {
    if (arr[n] < 0)return n;
    else return arr[n] = find(arr[n]);
}

void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)return;

    if (arr[a] < arr[b]) {
        arr[a] += arr[b];
        arr[b] = a;
    }
    else {
        arr[b] += arr[a];
        arr[a] = b;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, K;
    fill(arr, arr + 1001, -1);
    cin >> N >> K;
    int m;
    cin >> m;
    for (int i = 0; i < K; i++) {
        int a, b;
        cin >> a >> b;
        merge(a, b);
    }

    
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        u = find(u);
        v = find(v);

        if (u == v)cout << "Y" << '\n';
        else cout << "N" << '\n';
    }
    
}