axuhongbo的个人博客

#include <iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<bitset>
using namespace std;
#define lson root<<1
#define rson root<<1|1
#define MID int m = (l+r)/2;
const int inf = 0x3f3f3f3f;
const int mmax = 59999;
int f[150010];
int n,k;
int find(int x)
{
    if(x==f[x])
        return x;
    else
        return f[x] = find(f[x]);
}
bool same(int x,int y)
{
    return find(x)==find(y);
}
void unite(int x,int y)
{
    int u = find(x);
    int v = find(y);
    if(u!=v)
        f[u] = v;
}
int main()
{
    //x大y一个n代表x吃y
    //x,y相等代表同类
    //x小于y一个n代表y吃x
    //当然整体情况是%3n之后得出来的
    scanf("%d%d",&n,&k);
    int d,x,y;
    int ans=0;
    for(int i=1; i<=3*n; i++)
        f[i] = i;
    while(k--)
    {
        scanf("%d%d%d",&d,&x,&y);
        if(x>n||y>n||(d==2&&x==y))
        {
            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+n))
                ans++;
            else
            {
                unite(x+n,y);//代表x吃y的三种情况
                unite(x+2*n,y+n);
                unite(x,y+2*n);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}