[백준 7511번] 소셜 네트워킹 어플리케이션 (C++)

문제링크 : https://www.acmicpc.net/problem/7511

7511번: 소셜 네트워킹 어플리케이션

 

#include <bits/stdc++.h>
using namespace std;

int parent[100001]; 

int find_root(int x)
{
    if(x == parent[x]) return x;  //루트노드면 그대로 반환
    return find_root(parent[x]);  //자식노드면 부모노드로 다시 탐색
}

void Union(int a, int b)
{
    a = find_root(a);
    b = find_root(b);
    if(a!=b)
    {
        parent[a]=b;  //속한 트리가 다르다면 병합시킴 (Union)
    }
}

int linked(int a, int b)
{
    if(find_root(a) == find_root(b)) return 1;  //루트가 같다면 1반환
    return 0;

}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

     int T, N, K, A, B, M, U, V;
     cin >> T;
     for(int i=0; i<T; i++)
     {
        cin >> N >> K;
        for(int j=0; j<N; j++)
        {
            parent[j] = j;
        }

        while(K--)
        {
            cin >> A >> B;
            Union(A,B);   
        }
        cin >> M;
        cout << "Scenario " << i + 1 << ":" <<"\n"; 
        while(M--)
        {
            cin >> U >> V;
            cout << linked(U, V) <<"\n";
        }
        cout << "\n";
     }

    return 0;
}

 

분리집합의 웰노운 문제이다.

분리집합 알고리즘에 대해 잘 알고있다면 쉽게 풀지만 모른다면 알아야한다.

분리집합에 대해 이 문제로 처음 접했다보니 따로 알아봤다.