P1892 [BOI2003]团伙并查集

本文主要是介绍P1892 [BOI2003]团伙并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：
在这里插入图片描述
输入输出样例
input:
6
4
E 1 4
F 3 5
F 4 6
E 1 2
output:
3

思路：
并不是两个人一个团体，而是在一个团体中的人都需要是朋友。
把朋友（敌人的敌人=朋友）合并在一起。
代码：
错误：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define maxn 11111
using namespace std;
int n,m,mi,mj;
char c;
int fa[maxn],cnt[maxn];
vector<int> e[maxn];
int getfa(int x)
{return (x==fa[x])?x:(fa[x]=getfa(fa[x]));
}
void merge(int x,int y)
{int xx=getfa(x),yy=getfa(y);if (xx==yy) return;fa[xx]=yy;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++){cin>>c>>mi>>mj;if(c=='F') merge(mi,mj);else{if(e[mi].size()==1||e[mj].size()==1){if(e[mi].size()==1){merge(e[mi][0],mj);e[mi].pop_back();}if(e[mi].size()==1){merge(e[mj][0],mi);e[mi].pop_back();}  }else{e[mi].push_back(mj);e[mj].push_back(mi);}}}for(int i=1;i<=n;i++) cnt[getfa(i)]++;//for(int i=1;i<=n;i++) cout<<"i="<<i<<" "<<"cnt[i]"<<cnt[i]<<endl;int ans=0;for(int i=1;i<=n;i++)  if(cnt[i]) ans++;cout<<ans<<endl;return 0;
}

错误代码的问题在于第一次合并下x的敌人的时候清空了记录。
正解：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define maxn 11111
using namespace std;
int n,m,mi,mj;
char c;
int fa[maxn],cnt[maxn];
int e[maxn];
int getfa(int x)
{return (x==fa[x])?x:(fa[x]=getfa(fa[x]));
}
void merge(int x,int y)
{int xx=getfa(x),yy=getfa(y);if (xx==yy) return;fa[xx]=yy;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++){cin>>c>>mi>>mj;if(c=='F') merge(mi,mj);else{if(e[mi]) merge(e[mi],mj);else e[mi]=mj;if(e[mj]) merge(e[mj],mi);else e[mj]=mi;}}for(int i=1;i<=n;i++) cnt[getfa(i)]++;//for(int i=1;i<=n;i++) cout<<"i="<<i<<" "<<"cnt[i]"<<cnt[i]<<endl;int ans=0;for(int i=1;i<=n;i++)  if(cnt[i]) ans++;cout<<ans<<endl;return 0;
}