[BOJ/Gold 4] 백준 25187 고인물이 싫어요(C++)

문제 링크

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

 

 

문제

재형이는 청정수를 좋아하고 고인물을 싫어한다. 오늘도 청정수를 구하기 위해 물탱크들이 있는 마을에 방문한다.

마을에는 N개의 물탱크가 존재하고, 각 물탱크는 청정수 또는 고인물을 저장하고 있다. 그리고 물탱크는 공급의 편의를 위해 M개의 파이프로 서로 연결되어 있다.

청정수를 얻기 위해 K번 물탱크에 방문했을 때, K번 물탱크와 K번 물탱크에서 0개 이상의 파이프를 거쳐 이동 가능한 물탱크 중, 청정수가 담긴 물탱크의 수가 고인물이 담긴 물탱크의 수보다 더 많은 경우 청정수를 얻을 수 있다.

방문할 예정인 물탱크에 대한 정보가 주어질 때마다, 청정수를 얻을 수 있는지 구해보자. 

입력

첫째 줄에 물탱크의 수 N(1 ≤ N ≤ 100,000)과 파이프의 수 M(0 ≤ M ≤ 200,000), 그리고 물탱크에 방문할 횟수 Q(1 ≤ Q ≤ 100,000)가 주어진다. 

둘째 줄에 1번부터 N번 물탱크까지 순서대로 들어있는 물의 종류가 주어진다. 청정수는 1, 고인물은 0으로 주어진다. 

다음 3번째부터 M + 2번째 줄까지 파이프가 연결하는 두 물탱크의 번호 u, v(1 ≤ u, v ≤ N, u ≠ v)가 주어진다. 같은 두 물탱크를 연결하는 파이프가 여러 개 존재할 수 있다. 

 M + 3번째부터 M + Q + 2번째 줄까지 방문할 물탱크의 번호 K(1 ≤ K ≤ N)가 주어진다.  

출력

 Q개의 줄에 각 물탱크에 방문했을 때 청정수를 얻을 수 있다면 1을, 아니면 0을 주어진 정보 순서대로 출력한다. 

예제 입력 1

5 3 3
1 0 1 1 0
1 2
3 4
4 5
1
5
4

예제 출력 1

0
1
1

첫번째 쿼리는 1번 물탱크와 연결된 물탱크는 2번 물탱크 하나이므로, 고인물이 담긴 물탱크와 청정수가 담긴 물탱크의 수가 같다. 

두번째 쿼리는 5번 물탱크와 연결된 물탱크는 3, 4번 물탱크이므로, 고인물이 담긴 물탱크보다 청정수가 담긴 물탱크가 더 많다. 

예제 입력 2

5 5 3
1 0 1 1 0
1 2
1 3
1 4
2 3
3 4
1
5
4

예제 출력 2

1
0
1

알고리즘 분류

• 유니온 파인드

풀이

M개의 파이프에 대한 정보를 입력받고 양쪽 물탱크를 연결한다.

연결할 때, Parent가 되는 물탱크의 청정수 및 고인물의 개수에 대한 정보에 Child가 되는 물탱크의 정보들을 더한다.

마지막으로 Q번 물탱크를 방문하면서 방문하는 물탱크의 Parent가 되는 물탱크의 청정수와 고인물의 개수를 비교한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 100001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, Q, W, U, V, K;
int Parent[MAX], A[MAX], B[MAX];

int Answer;

void init() {
    for (int i = 0; i < MAX; i++) {
        Parent[i] = i;
    }
}

int find(int X) {
    if (Parent[X] == X) {
        return X;
    }
    return Parent[X] = find(Parent[X]);
}

void union_Group() {
    int PU = find(U);
    int PV = find(V);
    if (PU != PV) {
        if (PU > PV) {
            swap(PU, PV);
        }
        A[PU] += A[PV];
        B[PU] += B[PV];
        Parent[PV] = PU;
    }
}

void find_Answer() {
    int P = find(K);
    if (A[P] > B[P]) {
        cout << "1\n";
    }
    else {
        cout << "0\n";
    }
}

void input() {
    cin >> N >> M >> Q;
    for (int i = 1; i <= N; i++) {
        cin >> W;
        if (W == 1) {
            A[i]++;
        }
        else {
            B[i]++;
        }
    }
    while (M--) {
        cin >> U >> V;
        union_Group();
    };
    while (Q--) {
        cin >> K;
        find_Answer();
    };
}

int main() {
    FASTIO
    init();
    input();

    return 0;
}