P1892 [BOI2003] 团伙
如果你wa，可能是合并的顺序出错
[1,n]表示朋友,[n+1,2*n]表示敌人
如果a,b是朋友，直接合并a,b
如果a,b是敌人：
1.合并a+n和b，a的敌人是b的朋友
2.合并a和b+n，b的敌人是a的朋友
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int f[20005];int d[20005];
int find(int x) {
return x == f[x] ? x : f[x] = find(f[x]);
}
void unit(int x, int y) {
int fx = find(x), fy = find(y);
f[fx] = fy;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= 2 * n; i++) f[i] = i;
while (m--) {
int x, y;
char op;
cin >> op >> x >> y;
int fx = find(x), fy = find(y);
if (op == 'F') {//pengyou
if (fx != fy) {
unit(x, y);//可以不用再合并两者的敌人
}
}
else {//敌人
if (fx != fy) {
unit(x + n, y);//x的敌人是y的朋友
unit( y + n,x);//y的敌人是x的朋友，注意合并时两者的位置，不然会少因为它的祖先会到后面
}
}
}
int ans=0;
for (int i = 1; i <= n; i++) if(i==f[i]) ans++;
cout << ans;
return 0;
}