[洛谷P1892][codevs2597]团伙

题目大意：有n个强盗，他们有这样的关系:1.朋友的朋友是朋友；2.敌人的敌人是朋友。

两个人是朋友，则他们在一个团伙中，是敌人则在不同团伙中。

现在给出一些朋友或敌人的关系，问最多有多少团伙。输入保证无误。

解题思路：并查集。

如果a与b是朋友，则连接a和b。

如果a和b是敌人，则连接a和b+n，b和a+n。

那么当a和b是敌人，b和c是敌人时，a连接了b+n，c也连接了b+n，此时a和c在同一并查集当中，也就满足了“敌人的敌人是朋友”的条件。

最后扫一遍即可。

时间复杂度$O(n+m)$。

C++ Code：

#include<cstdio>

#include<cstring>

int n,q,fa[2005];

char op[5];

bool vis[2005];

int dad(int x){return fa[x]==x?x:fa[x]=dad(fa[x]);}

int main(){

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

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

	while(q--){

		scanf("%s",op);

		if(op[0]=='F'){

			int x,y;

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

			x=dad(x),y=dad(y);

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

		}else{

			int x,y;

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

			int a=dad(x),b=dad(y+n);

			if(a!=b)fa[b]=a;

			a=dad(x+n),b=dad(y);

			if(a!=b)fa[a]=b;

		}

	}

	memset(vis,0,sizeof vis);

	int ans=0;

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

		int a=dad(i);

		if(!vis[a]){

			++ans;

			vis[a]=true;

		}

	}

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

	return 0;

}

巴特西

[洛谷P1892][codevs2597]团伙

最新文章

热门文章