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

https://www.acmicpc.net/problem/7511

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

 

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. vect[ i ] = i 로 초기화합니다.

 

3. Union-Find를 활용하여 친구 관계를 이어주고, 부모 노드의 값이 같다면 1, 아니라면 0을 출력합니다.

 

[ 소스코드 ]

#include<iostream>
 
using namespace std;
 
int n, k, m;
int vect[1000001];
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 1; t <= T; t++) {
        scanf("%d", &n);
 
        for (int i = 1; i <= n; i++) {
            vect[i] = i;
        }
 
        scanf("%d", &k);
 
        for (int i = 0; i < k; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
 
            Union(a, b);
        }
 
        scanf("%d", &m);
 
        printf("Scenario %d:\n", t);
 
        for (int i = 0; i < m; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
 
            if (Find(a) != Find(b)) {
                printf("0\n");
            }
            else {
                printf("1\n");
            }
        }
 
        printf("\n");
    }
}