AcWing 784. 强盗团伙__最简明易懂的解法
原题链接
简单
作者:
编号002
,
2024-04-09 23:50:39
,
所有人可见
,
阅读 6
#include<iostream>
#include<vector>
using namespace std;
int fa[1010];
struct des
{
int x,y;
};
vector<des> t;
int find(int x)
{
if(fa[x]!=x)fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)fa[i]=i;
int a,b;
char op;
while(m--)
{
cin>>op>>a>>b;
if(op=='E')
{
for(int i=0;i<t.size();i++)
{
if(t[i].x==a) fa[find(b)]=find(t[i].y);
if(t[i].y==a) fa[find(b)]=find(t[i].x);
if(t[i].x==b) fa[find(a)]=find(t[i].y);
if(t[i].y==b) fa[find(a)]=find(t[i].x);
}
t.push_back({a,b}); //记录下哪两个人是敌人
}
else fa[find(a)]=find(b);
}
int cnt=0;
for(int i=1;i<=n;i++)
if(fa[i]==i)cnt++; //关键
cout<<cnt<<endl;
return 0;
}