若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;
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;
}
else
{
fa[ye]=xf;
fa[xe]=yf;
}
}
for(int i=1; i<=n; i++)
if(fa[i]==i) ++ans;
printf("%d", ans);
return 0;
}