题目网址 ：

这是一道利用并查集模拟的题目，也是并查集的裸题。

乍一看好像有点麻烦，因为会觉得动物们来回吃来吃去情况就会变得越来越复杂。

其实无论X和Y是同类还是捕食关系，归根结底都是集合合并的问题（捕食关系“错位”一下也是对等合并）。

考虑什么时候会发生冲突？冲突的情况只有一个，那就是两个有交集的食物链合并，并且合并的时候发生错位，也就是ABC不对等合并。另外的情况都是元素X所在的食物链和元素Y所在的食物链没有交集，这样合并后更新就好。

举个例子，就是你可以ABC和ABC合并， 也可以ABC和DEF合并，但是绝对不能ABC和BCA或者ACB合并。 原因是你现在获取了两个元素X和Y，他们俩要么处于同一个食物链中，要么处于不同食物链中，不同食物链可以直接合并，相同食物链只能对等合并（其实也就是不用合并），不能错位合并。

并查集是一种树结构，有一个特别典型的特性：只要不是根节点，就先获取根节点再做处理。

其实看过并查集的实现就会发现，如果一个节点不是根节点，那么跟这个节点有关的信息都是没意义的。因为并查集只保证根节点的信息具有时效性，其他非根节点的节点都只有一个作用，那就是找到根节点。

贴下代码，这个模拟的过程还是比较恶心人的。

#include 
    
     #include 
     
      using namespace std;const int maxn = 50050;int p[maxn], rank[maxn], prev[maxn], next[maxn];void makeset(int x){    p[x] = x;    rank[x] = 1;}int findset(int x){    int px = x, i;    while(p[px] != px) px = p[px];    while(x != px)    {        i = p[x];        p[x] = px;        x = i;    }    return px;}int unionset(int x, int y){    x = findset(x);    y = findset(y);    if(rank[x] > rank[y])    {        p[y] = x;        return x;    }    else    {        p[x] = y;        if(rank[x] == rank[y]) rank[y]++;        return y;    }}int main(){    // freopen("in.txt", "r", stdin);    int N, K;    cin >> N >> K;    for(int i = 1; i <= N; i++) makeset(i);    int ans = 0;    for(int i = 0; i < K; i++)    {        int D, X, Y;        scanf("%d%d%d", &D, &X, &Y);        if(X > N || Y > N) { ans++; continue; }        if(D == 1)        {            int x = findset(X), y = findset(Y);            if(x == y) continue;            if(y == prev[x] || y == next[x]) ans++;            else            {                int a = prev[x], b = x, c = next[x];                int d = prev[y], e = y, f = next[y];                int o, p, q;                if(a == 0) o = d;                else if(d == 0) o = a;                else o = unionset(a, d);                p = unionset(b, e);                if(c == 0) q = f;                else if(f == 0) q = c;                else q = unionset(c, f);                prev[p] = o; next[p] = q;                prev[o] = q; next[o] = p;                prev[q] = p; next[q] = o;            }        }        else        {            int y = findset(Y), x = findset(X);            if(x == y) ans++;            else            {                int a = x, b = next[x], c = prev[x];                int d = prev[y], e = y, f = next[y];                if(e == c || e == a) ans++;                else                {                    int o, p, q;                    if(b == 0) p = e;                    else p = unionset(b, e);                    if(d == 0) o = a;                    else o = unionset(a, d);                    if(c == 0) q = f;                    else if(f == 0) q = c;                    else q = unionset(c, f);                    prev[p] = o; next[p] = q;                    prev[o] = q; next[o] = p;                    prev[q] = p; next[q] = o;                }            }        }    }    cout << ans << endl;    return 0;}
     
    

记得对每个元素保存捕食它的集合和它捕食的集合，集合当然都是根节点，并查集保证这一点。