题目描述

解题思路：

把所有动物放到一个 集合中
根据 判断 元素 与 根节点的关系
找出各个元素 之间的联系

妙处所在：

并查集的思想
取余的环型
巧妙的路径压缩

C++ 代码

#include<iostream>
using namespace std;
const int N = 5e4 + 10;
int p[N], d[N];
int n, m;
int find(int x)//同时 对两个元素进行路径压缩 是真的 六
{
    if (x != p[x])
    {
        int t = find(p[x]);
        d[x] += d[p[x]];//精髓所在
        p[x] = t;
    }
    return p[x];
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)p[i] = i;
    int t, a, b,res=0;
    while (m--)
    {

        cin >> t >> a >> b;
        int pa = find(a), pb = find(b);
        if (a > n || b > n) { res++; continue; }
        if (t == 1)
        {
            if (pa == pb && (d[a] - d[b]) % 3)res++;//不成立的情况
            else if (pa != pb)//为真的 情况 根据 画图 加上定义可知道
            {
                p[pa] = pb;//有关系就放到一个集合中
                d[pa] = d[b] - d[a];
            }
        }
        if (t == 2)
        {
            if (pa == pb && (d[a] - d[b] - 1) % 3)res++;//这样写是因为可能有负数存在
            else if (pa != pb)
            {
                p[pa] = pb;//有关系就放到一个集合中去
                d[pa] = d[b] - d[a] + 1;
            }
        }
     }
    cout << res;
    return 0;
}
blablabla