AcWing 784. 强盗团伙-(菜鸡の理解
原题链接
简单
作者:
IsKomekko_
,
2022-02-25 19:27:53
,
所有人可见
,
阅读 247
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int p[N], e[N], num;
int find(int x)
{
if(x != p[x]) return p[x] = find(p[x]);
return p[x];
}
int main()
{
int n, m;cin >> n >> m;
for(int i = 1;i <= n;i ++) p[i] = i;
for(int i = 0;i < m;i ++)
{
char st;
int a, b;
cin >> st >> a >> b;
int pa = find(a), pb = find(b);
if(st == 'E')
{
if(!e[a]) e[a] = pb;
if(!e[b]) e[b] = pa;
int epa = find(e[a]), epb = find(e[b]);
if(pa != epb) p[pa] = epb;
if(pb != epa) p[pb] = epa;
}
else
{
if(pa != pb)
p[pa] = pb;
}
}
for(int i = 1;i <= n;i ++)
if(find(p[i]) == i) num ++;
cout << num;
return 0;
}
/*
本题关键在于处理E的情况
当A和B互为敌对关系时,
A的除B外的敌人就是B的朋友
所以我们必须要维护一个A的敌人集合e
以便为B找到朋友,进行合并
又知A的所有敌人是同属于同一个集合,因为他们都互相为朋友
所以集合e只需记录一个A的敌人即可反找到A的敌人集合的根节点,将B并入集合
这里需注意要对A的敌人和B的敌人都进行合并一次
*/