[POJ/1182] 먹이 사슬

### Union Find ###

- Union-Find 는 같은 그룹을 관리하는 자료구조.

[1182] 먹이사슬 : http://poj.org/problem?id=1182

- 이 문제의 경우, 같은 종류인지만 판단하는 것이 아니라 "먹는다" 라는 관계가 포함되어 있다.

- 각 동물 i에 대해 3개의 요소 i-A, i-B, i-C 를 만들어 3*n 개의 요소로 Union-Find 를 만든다.

- i-X 는 i가 종류 x인 경우를 표현한다.

- t == 1 : X Y가 같은 종류로, [X-A, Y-A] [X-B, Y-B] [X-C, Y-C] 의 3개의 페어를 유니온한다.

>> 모순이 발생하는지 확인하려면, [X-A, Y-B] 가 유니온 되어 있는지 확인하면 된다.

- t == 2 : X 가 Y를 먹는다. [X-A, Y-B] [X-B, Y-C] [X-C, Y-A] 의 3개의 페어를 유니온한다. 

>> 모순이 발생하는지 확인하려면, [X-A, Y-A] 가 유니온 되어 있는지 확인하면 된다.

referenced by 노란책.

<소스코드>

#include <stdio.h>
 
int n, k;
int p[500001*3];
 
int safe(int x)
{
    return (0 <= x && x < n);
}
 
int find(int x)
{
    return p[x] = p[x] == x ? x : find(p[x]);
}
 
int same(int x, int y)
{
    x = find(x);
    y = find(y);
    return x == y;
}
 
void Union(int x, int y)
{
    x = find(x);
    y = find(y);
    p[x] = y;
}
 
int main()
{
    int ans=0;
    scanf("%d%d", &n, &k);
 
    for(int i=1; i<=n*3+1; i++) 
        p[i] = i;
 
    while(k--) {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);
        x--; y--; // [0, n)
 
        if(!safe(x) || !safe(y)) ans++;  
        else {
            if(t == 1) { // x == y
                if(same(x, y+n) || same(x, y+2*n)) ans++;
                else {
                    Union(x, y);
                    Union(x+n, y+n);
                    Union(x+2*n, y+2*n);
                }
            }
            else { // x > y
                if(same(x, y) || same(x, y+2*n)) ans++;
                else {
                    Union(x, y+n);
                    Union(x+n, y+2*n);
                    Union(x+2*n, y);
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}
 

>> 예를들어 설명하면, N=100 인 경우를 생각해보자.

1) 1과 2가 같은 종류라면, Union(1, 2), Union(101, 102), Union(201, 202) 가 진행된다.

2) 1이 2를 잡아먹는다면, Union(1, 102], Union(101, 202), Union(201, 2) 가 진행된다.

1) t == 1 은 x 와 y가 같은 종류인지 묻는 상태.

>> same(x, y*n) 은 x가 y를 잡아먹는 관계인지 확인.

>> same(x, y*2*n) 은 y가 x를 잡아먹는 관계인지 확인하는 케이스이다. (58라인 참고)

2) t==2 인경우는 x가 y를 잡아먹는지 묻는 상태.

>> same(x, y) 는 x가 y와 같은 종류인지 확인

>> same(x, y+2*n) 은 y가 x를 잡아먹는지 확인