[算法竞赛进阶指南]0x41-食物链

题意：

有一串关系：

1. 1 x y，表示x和y是同类。
2. 2 x y，表示x吃y。

这串关系中，如果x吃y，y吃z，那么z必定吃x，形成一个环。
现在给定k个关系，问有几个关系是错误的。

分析：

扩展域并查集，将一个点分成三个点，分别判断属于不同类别的点之间是否满足一定约束关系。

代码：

#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 +7;
//constexpr int mod2 = 998244353;
constexpr int MAXNe5 = 1e5 +7;
constexpr int MAXNe6 = 1e6 + 7;
typedef long long ll;
#pragma region 
inline long long read() {
    char c = getchar();long long flag = 1, ans = 0;
    while(c < '0' || c > '9'){if(c == '-') flag = -1; c = getchar();}
    while(c >= '0' && c <= '9'){ans = ans * 10 + c - '0'; c = getchar();}
    return (ans * flag);
}
#pragma endregion
// C'est la vie
int fa[MAXNe6];
void init() {
    for(int i = 1; i < MAXNe6; ++ i) fa[i] = i;
}

int find(int x) {
    return (fa[x] == x) ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    fa[find(x)] = find(y);
}

int main() {
    int n = read(), k = read(), ans = 0;
    init();
    while(k --) {
        int d, x, y;
        cin >> d >> x >> y;
        if(x > n || y > n || (d == 2 &&  x == y)) ans ++;
        else {
            if(d == 1) {
                int fax = find(x), fay = find(y);
                int fax2 = find(x + n), fay2 = find(y + n);
                if(fax2 ==  fay || fay2 == fax) ans ++;
                else {
                    merge(x, y);
                    merge(x + n, y + n);
                    merge(x + 2 * n, y + 2 * n);
                }
            } else {
                int fax = find(x), fay = find(y);
                int fax2 = find(x + n), fay2 = find(y + n);
                if(fax == fay || fax == fay2) ans ++;
                else {
                    merge(x + n, y);
                    merge(x + 2 * n, y + n);
                    merge(y + 2 * n, x);
                }
            }
        }
    }
    cout << ans << endl;
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
}