POJ 1182 Food Chain ( Union Find )

1182 -- 食物链
這題解法我覺得很特別，是要維護哪些情報有相互證明的關係，哪些情報有相互排斥的關係，哪些情報沒有關係。這些都可以透過並查集的一些小技巧解決。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 4;
const int MAXK = 1e5 + 5;

int n, k;

struct UnionFind{
    int fa[ MAXN ];
    void init(int p){
        for(int i = 1; i <= p; ++i)
            fa[ i ] = i;
    }
    int find(int x){ return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] ); }
    bool unite(int x, int y){
        int a = find( x );
        int b = find( y );
        if( a == b ) return false;
        fa[ a ] = b; return true;
    }
} uf;

int getidx(int idx, int type){
    return idx * 3 - type;
}

int main(){
    int ans = 0;
    scanf("%d%d", &n, &k);
    uf.init( n * 3 );
    for(int i = 0; i < k; ++i){
        int op, x, y; scanf("%d%d%d", &op, &x, &y);
        if( x > n || y > n ){
            ++ans;
            continue;
        }
        if( op == 1 ){
            if( uf.find( getidx( x, 0 ) ) == uf.find( getidx( y, 1 ) ) ||
                uf.find( getidx( x, 0 ) ) == uf.find( getidx( y, 2 ) ) ){
                ++ans;
                continue;
            }
            for(int i = 0; i < 3; ++i)
                uf.unite( getidx( x, i ), getidx( y, i ) );
        } else{
            if( uf.find( getidx( x, 0 ) ) == uf.find( getidx( y, 0 ) ) ||
                uf.find( getidx( x, 0 ) ) == uf.find( getidx( y, 2 ) ) ){
                ++ans;
                continue;
            }
            for(int i = 0; i < 3; ++i)
                uf.unite( getidx( x, i ), getidx( y, ( i + 1 ) % 3 ) );
        }
    }
    printf("%d\n", ans);
    return 0;
}