[Luogu 2024] 食物链

<题目链接>

---

---

题解

#include <cstdio>

const int MAXN=50010;

int n,k,ans;

class UFS

{

	private:

		int f[MAXN*3];

		int Find(int x)

		{

			return x==f[x] ? x : f[x]=Find(f[x]);

		}

		void Union(int x,int y)

		{

			f[Find(y)]=Find(x);

		}

	public:

		UFS(int n)

		{

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

				f[i]=i;

		}

		void UnionSame(int x,int y)

		{

			Union(x,y);

			Union(x+n,y+n);

			Union(x+(n<<1),y+(n<<1));

		}

		void UnionEat(int x,int y)

		{

			Union(x+n,y);

			Union(x+(n<<1),y+n);

			Union(x,y+(n<<1));

		}

		bool Connected(int x,int y)

		{

			return Find(x)==Find(y);

		}

};

int main(int argc,char** argv)

{

	scanf("%d %d",&n,&k);

	static UFS *S=new UFS(n);

	for(int i=1,opt,x,y;i<=k;++i)

	{

		scanf("%d %d %d",&opt,&x,&y);

		if(x>n || y>n)

		{

			++ans;

			continue;

		}

		if(opt==1)

			if(S->Connected(x,y+n) || S->Connected(x+n,y))

				++ans;

			else

				S->UnionSame(x,y);

		else

			if(S->Connected(x,y) || S->Connected(x,y+n))

				++ans;

			else

				S->UnionEat(x,y);

	}

	printf("%d\n",ans);

	delete S;

	return 0;

}