信息学奥赛一本通 1385：团伙(group)

信息学奥赛一本通 1385：团伙(group)

【题目链接】

ybt 1385：团伙(group)
洛谷 P1892 [BOI2003]团伙

【题目考点】

1. 并查集

【解题思路】

每个人是一个元素，一个团伙是一个集合。

• 如果A与B是朋友，那么A与B同属于一个集合，应该将A所在的集合与B所在的集合合并。
• 如果A与C是敌人，A与D是敌人，根据“我敌人的敌人是我的朋友”，A是C的敌人，D是C的敌人（A）的敌人，因此D与C是朋友。
  同理，A的所有敌人都是朋友，只需要知道A的一个敌人，通过并查集中的查询操作，就能够知道A的敌人组成的集合是什么。

也就是说一个人的所有敌人都互为朋友，同属于一个集合。

因此，设数组enemy， enemy[i]表示i的某一个敌人。
当x与y互为敌人时，先考虑y作为x的敌人的情况：

• 如果x还没有敌人(enemy[x] == 0)，就将y设为x的一个敌人，即enemy[x]=y
• 如果x已有敌人(enemy[x] > 0)，那么应该将y加入x的敌人组成的集合，即将y与enemy[x]所在的集合合并。

反过来，同时要考虑x作为y的敌人的情况：

• 如果y还没有敌人(enemy[y] == 0)，就将x设为y的一个敌人，即enemy[y]=x
• 如果y已有敌人(enemy[y] > 0)，那么应该将x加入y的敌人组成的集合，即将x与enemy[y]所在的集合合并。

并查集中每个集合的根结点满足fa[i] == i，集合的数量就是fa数组中根结点的个数。
最后输出集合的数量。

【题解代码】

#include<bits/stdc++.h>
using namespace std;
#define N 1005
int n, m, fa[N], enemy[N];//fa[i]：i的双亲 enemy[i]：i的某个敌人 
void init(int n)
{for(int i = 1; i <= n; ++i)fa[i] = i;
}
int find(int x)//查找x所在集合的根结点
{if(fa[x] == x)return x;return fa[x] = find(fa[x]);
} 
void merge(int x, int y)//合并x，y所在的集合
{fa[find(x)] = find(y);	
} 
int main()
{char opt;int p, q, ct = 0;cin >> n >> m;init(n);for(int i = 1; i <= m; ++i){cin >> opt >> p >> q;if(opt == 'F')merge(p, q);else //opt = 'E' 敌人 {if(enemy[p])//如果p有敌人enemy[p] merge(enemy[p], q);//将q加入到p敌人组成的集合 else//如果p没有敌人 enemy[p] = q;//q作为p的敌人 if(enemy[q])merge(enemy[q], p);elseenemy[q] = p;}}for(int i = 1; i <= n; ++i)if(fa[i] == i)//i是根结点 ct++;cout << ct;return 0;
}