并查集

这是一道比较特殊的并查集，开一个三倍的数组， 1～n保存同类，n～n×2保存猎物，n2~n3保存天敌；

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAXN=300005;

int read(){

	int rv=0,fh=1;

	char c=getchar();

	while(c<'0'||c>'9'){

		if(c=='-') fh=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9'){

		rv=(rv<<1)+(rv<<3)+c-'0';

		c=getchar();

	}

	return rv*fh;

}

int fa[MAXN],n,k,tot;

int find(int x){

	if(fa[x]!=x) fa[x]=find(fa[x]);

	return fa[x];

}

void merge(int x,int y){

	int r1=find(x),r2=find(y);

	if(r1!=r2){

		fa[r1]=r2;

	}

}

int main(){

	freopen("in.txt","r",stdin);

	n=read();k=read();

	for(int i=1;i<=n*3;i++){

		fa[i]=i;

	}

	for(int i=1;i<=k;i++){

		int t=read(),a=read(),b=read();

		if(t==2&&a==b){

			tot++;continue;

		}

		if(a>n||b>n){

			tot++;continue;

		}

		if(t==1){

			if((find(a)!=find(b+n))&&(find(a+n)!=find(b))&&(find(a)!=find(b+n*2))&&(find(a+n*2)!=find(b))){

				merge(a,b);

				merge(a+n,b+n);

				merge(a+n*2,b+n*2);

			}else{

				tot++;continue;

			}

		}else {

			if((find(a)!=find(b))&&(find(b+n)!=find(a))&&(find(a+n*2)!=find(b))){

				merge(a+n,b);

				merge(b+n*2,a);

				merge(b+n,a+n*2);

			}else tot++;

		}

	}

	cout<<tot;

	fclose(stdin);

	return 0;

}