求助:为什么两个人是朋友,不能把他们的敌人也合并
查看原帖
求助:为什么两个人是朋友,不能把他们的敌人也合并
438461
liu_chen_hao楼主2022/6/27 21:13

若A与B是朋友,C是A的敌人,D是B的敌人,则CD之间只能是朋友关系,否则会出现矛盾(假设C与D是敌人关系,那么A的敌人C的敌人D应是A的朋友,又有B的朋友A的朋友D是B的朋友,推出B与D是朋友关系,矛盾,则假设不成立,故CD只能是朋友关系)。 但是却不能将CD合并,请问这是为什么?

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;

int n,m,fa[N<<1],x,y,ans;
int xf,yf,xe,ye;   // f表示friend,e表示enemy 
char op;

int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
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++)
	{
		cin>>op>>x>>y;
		xf=find(x);
		yf=find(y);
		xe=find(x+n);
		ye=find(y+n);
		if(op=='F')
		{
			fa[xf]=yf;
			//fa[xe]=ye;    //这一行加上就错了, but why??? 
		}
		else
		{
			fa[ye]=xf;
			fa[xe]=yf;
		}
	}
	for(int i=1; i<=n; i++)
		if(fa[i]==i) ++ans;
	printf("%d", ans);

	return 0;
}
2022/6/27 21:13
加载中...