BOI2003 洛谷1892 （并查集入门）团伙

题目链接：[BOI2003]团伙 - 洛谷

首先对于两个人，如果是朋友关系的话，那么就直接用并查集并在一起就好了。但是如果是敌人关系那么在操作的时候就会复杂一点了，我们先使用一个数组来记录每个人的敌人有哪些，vis1[这个人的编号][第几个敌人] = 敌人的编号。那么我们在处理敌人关系的时候 ，例如a和b是敌人，那么就用并查集把a和b的所有敌人并在一起。再把b和a的所有敌人并在一起。最后再统计答案的时候就看看有多少人的fa[i] = i即为答案的数量。

code：

#include 
using namespace std;
int fa[1000010];
int vis1[1010][1000];
int fin(int x) {if(x != fa[x]) {return fa[x] = fin(fa[x]);  //并查集操作}return fa[x];
}
void unin(int x,int y) {   // 合并的操作x = fin(x);y = fin(y);fa[y] = x;
}
int a;
int b;
int cnt[100010];
int main() {cin>>a>>b;char qaq;int x,y;for(int i = 1;i <= a;i ++) {fa[i] = i;}for(int i = 1;i <= b;i ++) {cin>>qaq>>x>>y;if(qaq == 'F')unin(x,y);else {if(cnt[x])         // cnt用于记录这个人敌人的数量。for(int j = 1;j <= cnt[x];j ++)unin(y, fin(vis1[x][j]));if(cnt[y])for(int j = 1;j <= cnt[y];j ++) {   //合并敌人的敌人unin(x, fin(vis1[y][j]));}vis1[x][++ cnt[x]] = y;vis1[y][++ cnt[y]] = x;}}int ans = 0;for(int i = 1;i <= a;i ++) {if(fa[i] == i)   //统计答案ans ++;}cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！