题解 P2024 【食物链】

藕丝炖刺猬 · 2017-10-05 12:43:32 · 题解

//带权并查集    详细的看代码里的注释
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
int fa[50005],ran[50005];                                   //ran指种族 
int n,k;
int get_fa(int x)
{
    if(fa[x]==x) return x;
    int f=fa[x];
    fa[x]=get_fa(fa[x]);                                    //路径压缩 
    ran[x]=(ran[x]+ran[f])%3;
    return fa[x];                                    
}
bool judge(int c,int x,int y)                        
{
    int a=get_fa(x),b=get_fa(y);
    //cout<<a<<" "<<ran[x]<<" "<<b<<" "<<ran[y]<<endl; 
    if(a==b)                                                 //说明已经过确定关系了 
    {
        if(c==1)
        {
            if(ran[x]!=ran[y]) return false;
        }
        if(c==2)
        {
            if(ran[x]==1&&ran[y]!=0) return false;
            if(ran[x]==2&&ran[y]!=1) return false;
            if(ran[x]==0&&ran[y]!=2) return false;
        }
        return true;
    }
    else{                                                     //说明没有确定过关系 
        fa[a]=b;
        //cout<<c<<" "<<ran[x]<<" "<<ran[y]<<endl;
        if(c==2) ran[a]=(ran[y]-ran[x]+3+1)%3;
        if(c==1) ran[a]=(ran[y]-ran[x]+3)%3;
        //cout<<fa[a]<<ran[a]<<endl;
        a=get_fa(x); b=get_fa(y);
        //cout<<"changed:"<<a<<" "<<ran[x]<<" "<<b<<" "<<ran[y]<<endl;
        return true;
    }
}
int main()
{
    cin>>n>>k;
    int ans=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=k;i++)
    {
        int c,a,b;
        scanf("%d %d %d",&c,&a,&b);
        if(a>n||b>n) ans++;
        else if(c==2 && a==b) ans++;
        else if(judge(c,a,b)) continue;
        else ans++;
    }
    printf("%d\n",ans);
    return 0;
}