记录编号	510296	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]食物链	最终得分	100
用户昵称	leon	是否通过	通过
代码语言	C++	运行时间	0.089 s
提交时间	2018-09-18 21:32:26	内存使用	1.08 MiB

#include<iostream>
#include<algorithm>
#include<stdio.h>
#define maxn (50005)
using namespace std;
int n,m,fa[4*maxn],ans;
void init()
{
    for (int i=1;i<=4*n;i++)
    fa[i]=i;
}
int find(int x)
{
    if (fa[x]==x) return fa[x];
    return fa[x]=find(fa[x]);
}
void unio(int x,int y)
{
    fa[find(x)]=find(y);
    return ;
}
int pan1(int x,int y)//判断　　ｘ与ｙ是同类　　是否是真话
{
    if (x>n || y>n || x<=0 ||y<=0) return 0;
    if (find(x+n)==find(y) || find(x+2*n)==find(y)) return 0;
    //如果　ｘ所吃的东西与ｙ是同类　或　吃ｘ的东西与ｙ是同类，返回０（假话）
    return 1; 
}
int pan2(int x,int y)//判断　　ｘ吃ｙ　　是否是真话
{
        if (x>n || y>n || x<=0 ||y<=0 || x==y) return 0;
    if (find(x)==find(y) || find(x+2*n)==find(y)) return 0;
    //ｘ与ｙ是同类，或，ｙ与吃ｘ的东西是同类，则返回０（是假话）
    return 1;
}
int main()
{
freopen("eat.in","r",stdin);
freopen("eat.out","w",stdout);
    scanf("%d%d",&n,&m);
    init();ans=0;
    for (int i=1;i<=m;i++)
    {
        int p,x,y;
        scanf("%d%d%d",&p,&x,&y);
        if (p==1) 
        {
            if (pan1(x,y))
            {
                //要注意同时将三个集合全部重合
                unio(x,y);
                unio(x+n,y+n);
                unio(x+2*n,y+2*n);
            }
            else
            ans++;
        }
        else
        {
            if (pan2(x,y))
            {
                unio(x+n,y);//ｙ与ｘ吃的东西连接
                unio(x+2*n,y+n);//ｙ吃的东西与吃ｘ的东西连接
                unio(x,y+2*n);//ｘ与吃ｙ的东西连接
            }
            else
            ans++;
        }
    }
    printf("%d\n",ans);
}