并查集解决食物链问题，p88

#include <iostream>
using namespace std;
static const int MAX = 5000;
static const int INF = (1 << 20);
int par[MAX];    //父亲
int Rank[MAX];
//初始化n 个元素
void initi(int n){
    for(int i = 0; i < n; i++){
        par[i] = i;
        Rank[i] = 0;
    }
} 
//查询树的根
int Find(int x){
    if(par[x] == x) return x;
    else  return par[x] = Find(par[x]); 
} 
//合并x 和 y所属的集合
void unite(int x, int y){
    x = Find(x);
    y = Find(y);
    if(x == y) return;
    if(Rank[x] < Rank[y]) par[x] = y;
    else{
        par[y] = x;
        if(Rank[x] == Rank[y]) Rank[x]++;
    }
} 
//判断x 和 y 是否属于同一个集合
bool same(int x, int y){
    return Find(x) == Find(y);
} 
int N,K;
int T[MAX], X[MAX], Y[MAX];
int main(){
    cin >> N >> K;
    for(int i = 0; i < K; i++){
        cin >> T[i] >> X[i] >> Y[i];
    }    
    //初始化并查集
    //元素x, x + N, x + 2 * N 分别代表 x-A, x - B, x - C
    initi(3 * N);
    int ans = 0;        //不正确的信息数目
    for(int i = 0; i < K; i++){
        int t = T[i];
        int x = X[i] - 1, y = Y[i] - 1;        //把输入变成0， ...N-1的范围
        //不正确的编号
        if(x < 0 || x >= N || y < 0 || y >= N){
            ans++;
            continue;
        } 
        if(t == 1){
            //x 和 y 属于同一类的信息
            if(same(x, y + N) || same(x, y + 2 * N)) ans++;
            else{
                unite(x, y);
                unite(x + N, y + N);
                unite(x + 2 * N, y + 2 * N); 
            } 
        }
        else{
            //x 吃 y 的信息
            if(same(x, y) || same(x, y + 2 * N)){
                ans++;
            } 
            else{
                unite(x, y + N);
                unite(x + N, y + 2 * N);
                unite(x + 2 * N, y);
            }
        }
    } 
    cout << ans << endl;
}