【Luogu P2024&P1892】食物链&团伙（并查集拓展域）

Luogu P1892

Luogu P2024

这两道一眼看过去很容易发现可以用并查集来做——但是当我们仔细阅读题面后，会发现其实并没有那么简单。

我们知道并查集可以很轻松地维护具有传递性的信息，也就是“朋友的朋友就是我的朋友”这样的关系，但是普通的并查集并不能维护“敌人的敌人是朋友”这种关系。

这时候我们就要引入一种神奇的操作，将并查集扩大一倍，将增加的这一倍空间来维护节点i的敌人。

例如对于团伙这一题

	if (c=='F')

		{

			merge(x,y);

		}

		else

		{

			merge(x,y+n);

			merge(y,x+n);

			//x+n代表的是x的敌人集合

		}

非常好理解，确实是一种相当高效的操作。

P1892完整代码

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=2001;

int fa[maxn],n,m,cnt,x,y;

int getf(int v)

{

	if (fa[v]==v) return fa[v];

	return fa[v]=getf(fa[v]);

}

inline void merge(int x,int y)

{

	fa[getf(y)]=getf(x);

}

inline bool check(int x,int y)

{

	if (getf(x)==getf(y)) return true;

	return false;

}

int main()

{

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

	for (int i=1;i<=2*n;i++) fa[i]=i;

	for (int i=1;i<=m;i++)

	{

		char c;

		scanf("\n%c %d %d",&c,&x,&y);

		if (c=='F')

		{

			merge(x,y);

			//merge(x+n,y+n);

			//注意上面这句不能要，因为题目中没有说到朋友的敌人也是我的敌人。

		}

		else

		{

			merge(x,y+n);

			merge(y,x+n);

		}

	}

	for (int i=1;i<=n;i++) fa[i]=getf(i);//路径压缩，防止压缩不完全

	for (int i=1;i<=n;i++) if (fa[i]==i) cnt++;

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

	return 0;

}

P2024完整代码

#include<iostream>

#include<cstdio>

using namespace std;

const int maxn=3*5*1e4+10;

int fa[maxn],cnt,n,k,flag,x,y;

int getf(int v)

{

	if (fa[v]==v) return v;

	return fa[v]=getf(fa[v]);

}

inline void merge(int x,int y)

{

	x=getf(x);

	y=getf(y);

	fa[x]=y;

}

inline bool check(int x,int y)

{

	x=getf(x);

	y=getf(y);

	if (fa[x]==fa[y]) return true;

	return false;

}

int main()

{

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

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

		fa[i]=i;

	//i+n是i吃的集合，i+2n是吃i的集合

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

	{

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

		if (x>n||y>n) {cnt++;continue;}

		if (flag==1)

		{

			if (check(x+n,y)) {cnt++;continue;}

			if (check(x+2*n,y)) {cnt++;continue;}

			merge(x,y);

			merge(x+n,y+n);

			merge(x+2*n,y+2*n);

		}

		if (flag==2)

		{

			if (check(x,y)) {cnt++;continue;}

			if (check(y+n,x)) {cnt++;continue;}

			merge(x+n,y);

			merge(y+2*n,x);

			merge(x+2*n,y+n);

		}

	}

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

	return 0;

}

巴特西

【Luogu P2024&P1892】食物链&团伙（并查集拓展域）

最新文章

热门文章