本文共 1560 字，大约阅读时间需要 5 分钟。

参考：《挑战程序设计竞赛》

这本大佬写的书上面的办法，并没有去刻意的去保存权，来回地更改权值，已达到修改捕食关系的目的。详解如下：

前面的输入的决定了后面的正确与否，前面的输入具有不确定性，这点是题目的要求：“ 当前的话与前面的某些真的话冲突，就是假话； ”

思路： 第一组假设是D为1的情况，也就是两个是同一类的情况，反正没说是这个同一类属于ABC中的哪一类，所以有三种可能，把这三种可能都压进去。怎么压呢？核心来了！ 开辟一个3*N数组，1…N代表A类，N+1…2N代表B类，2N+1…3N代表C类。 1）第一种，x和y属于同一种类———合并x-A和y-A、x-B和y-B、x-C和y-C。

2）第二种，x吃y—————————合并x-A和y-B、x-B和y-C、x-C和y-A。

压入的时候，要先判断是否这句话为假话。假如说输入了第一种情况 x，y是否同一类，要判断x-A和y-B，X-A和y-C是否在集合里了，

为什不判断x-B和y-C，x-B和y-A； x-C和y-A，x-C和y-B? 因为压入的时候，就是按照三种可能压入的，所以只需判断一种情况就行了，另外两种不用判断。

#include
   
    #include
    
     #include
     
      using namespace std;int s[150300];int Find(int x){    if (s[x] < 0)return x;    else return s[x]= Find(s[x]);//路径压缩}void unite(int x, int y){    int rootx = Find(x);    int rooty = Find(y);    if (rootx != rooty)        s[rootx] = rooty;}bool same(int x, int y){    return Find(x) == Find(y);}int main(){    int N, K, D, x, y, ans = 0;    cin >> N >> K;    fill(s+1, s+3*N+1, -1);    while(K--)    {        scanf("%d%d%d", &D, &x, &y);        if (x > N || y > N) { ans++; continue; }        if (D == 1)        {            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        {            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<
     
    
   

转载地址：http://dkyci.baihongyu.com/