먹이사슬

이 문제 는 병집 한 약간 어려운 응용 프로그램 이다. 왜냐하면 세 가지 요소 가 있기 때문 이다. 상세한 코드 와 설명 은 아래 와 같다

#include <iostream>
#include <stdio.h>
using namespace std;
int pre[150005];
int find(int x)
{
    int r=x;
    while(r!=pre[r])
    {
        r=pre[r];
    }
    int i=x,j;
    while(pre[i]!=r)
    {
        j=pre[i];
        pre[i]=r;
        i=j;
    }
    return r;
}
void join(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)
        pre[fy]=fx;
}
bool same(int x,int y)
{
    return find(x)==find(y);
}
int main()
{
    int n,k,x,y,d;
    scanf("%d%d",&n,&k);
    {
        //       B A x，C B x+n，A C x+2n
        int sum=0;
        for(int i=1; i<=3*n; i++)//            x，x+n，x+2n  
            pre[i]=i;
        for(int i=1; i<=k; i++)
        {
            scanf("%d%d%d",&d,&x,&y);
            if(x<=0||y<=0||x>n||y>n)//        ，  
            {
                sum++;
                continue;
            }
            if(d==1)
            {
                if(same(x,y+n)||same(x+n,y+2*n)||same(x+2*n,y)||same(x,y+2*n)||same(x+n,y)||same(x+2*n,y+n))
                {//           ，      
                    sum++;
                    continue;
                }
                join(x,y);//         
                join(x+n,y+n);
                join(x+2*n,y+2*n);
            }
            else if(d==2)
            {
                if(x==y||same(x,y+2*n)||same(x,y)||same(x+n,y)||same(x+n,y+n)||same(x+2*n,y+n)||same(x+2*n,y+2*n))
                {//                ，    
                    sum++;
                    continue;
                }
                join(x,y+n);
                join(x+n,y+2*n);
                join(x+2*n,y);
            }

        }
       printf("%d
",sum);
    }
return 0;
}