题目描述

blablabla

样例

blablabla
#include <iostream>
using namespace std;

const int N = 50010;
int p[N],d[N];

int find(int x)
{
    if(p[x] != x)
    {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) p[i] = i;
    int res = 0;
    while(m--)
    {
        int t,x,y;
        scanf("%d%d%d",&t,&x,&y);
        if(x>n || y>n) res++;
        else
        {
            int px = find(x),py = find(y);
            if(t == 1)
            {
                if(px == py && (d[x]-d[y])%3)
                {
                    res++;
                }
                else if(px != py)
                {
                    p[p[x]] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else

            {
                if(px == py && (d[x]-d[y]-1)%3)
                {
                    res++;
                }
                else if(py != px)
                {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }
    printf("%d\n",res);
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla