【洛谷P1892】团伙

题目大意：维护 N 个人和 M 个关系，对每个人来说符合：我朋友的朋友也是我的朋友，我敌人的敌人也是我的朋友，求最多有多少个朋友构成的联通块。

题目大意：维护关系显然要用到并查集，这里是维护了两种关系，即：朋友和敌人，应该有两种做法，首先是维护带权并查集，可用 0 表示两人为朋友，1 表示两人为敌人，不过这样做似乎对于求有多少个朋友构成的联通块并不容易，因为只要两个人有关系（无论什么关系）都在一个联通块中；另一种做法就是扩展域并查集，将一个点拆成两个点，分别表示自己朋友的集合和自己敌人的集合，这样最后统计自己朋友的集合有多少联通块直接排序去重即可。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=1010;

int n,m,f[maxn<<1],a[maxn];

char opt[5];

int find(int x){

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

}

void read_and_parse(){

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

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

}

void solve(){

	int x,y;

	while(m--){

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

		if(opt[0]=='F')f[find(x)]=find(y);

		else f[find(x)]=find(y+n),f[find(x+n)]=find(y);

	}

	for(int i=1;i<=n;i++)a[i]=find(i);

	sort(a+1,a+n+1);

	printf("%d\n",unique(a+1,a+n+1)-a-1);

}

int main(){

	read_and_parse();

	solve();

	return 0;

}

巴特西

【洛谷P1892】团伙

最新文章

热门文章