[백준 12877] 먹이 사슬

문제

www.acmicpc.net/problem/12877

 

알고리즘

union find

 

풀이

N개의 동물들과 각 관계를 설명하는 K개의 정보가 주어질 때, 모순이 되는 정보들의 갯수를 세는 문제입니다.

 

문제가 되는 것은 2번 타입의 정보입니다. 동물들마다 3개의 노드를 갖도록 합시다 . 각각은 $i$번째 동물의 타입을 가리키게 됩니다. 구체적으로 $i$번째 동물이 A종류일때는 배열 $i$번이 정보를 갖고 있고 B, C 종류일때는 각각 $i+N$, $i+2*N$ 배열이 정보를 담고 있습니다. 이제 $union$함수를 통해 묶인 그룹은 해당 정보가 동시에 발생한다는 의미를 담는다고 합시다. 이렇게 되면 2번 정보또한 처리가 가능해집니다. 2 X Y가 입력으로 들어왔다면 아래 세 정보를 유니온 해주면 됩니다.

 

X Y+N

X+N Y+2*N

X+2*N Y

 

1번 정보는 X와 Y가 같으므로 다음과 같은 정보를 유니온 하면 됩니다.

 

X Y

X+N Y+N

X+2*N Y+2*N

 

각 정보에 따른 모순을 검사해주며 답을 카운트해주면 됩니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

int N, K, ans;
int p[150000];

bool inr(int x) {
    return 0 <= x && x < N;
}

int find(int x) {
    return p[x] < 0 ? x : (p[x] = find(p[x]));
}

void _union(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y)
        return;
    if (-p[x] < -p[y])
        swap(x, y);
    p[x] += p[y];
    p[y] = x;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N >> K;
    memset(p, -1, sizeof(p));
    while (K--) {
        int t, x, y;
        cin >> t >> x >> y;
        --x, --y;
        if (!inr(x) || !inr(y)) {
            ans += 1;
            continue;
        }
        if (t == 1) {
            if (find(x) == find(y + N) || find(x) == find(y + 2 * N)) {
                ans += 1;
            } else {
                _union(x, y);
                _union(x + N, y + N);
                _union(x + 2 * N, y + 2 * N);
            }
        } else {
            if (find(x) == find(y) || find(x) == find(y + 2 * N)) {
                ans += 1;
            } else {
                _union(x, y + N);
                _union(x + N, y + 2 * N);
                _union(x + 2 * N, y);
            }
        }
    }
    cout << ans;
    return 0;
}

 

++

프로그래밍 콘테스트 챌린징 책을 참고하여 작성했습니다.