讨论 / 有点麻烦(并查集)
沧海一声喵 2018-02-27 02:12:58
点我顶贴 收藏 删除
#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

typedef struct node{

int x,y;

}node;

vector<int> e[1005];

int n,m,f[1005];node h[5005];

int find(int x){

if(x!=f[x]) return find(f[x]);

else return x;}

int main(){

int i,j,x,y,fx,fy,max=0,num[1005]={0},p=0;

char c;

cin>>n>>m;

for(i=1;i<=n;i++) f[i]=i;

for(i=1;i<=m;i++){

cin>>c>>x>>y;

if(c=='F'){

fx=find(x);fy=find(y);

if(fx!=fy) f[fx]=fy;}

if(c=='E'){

h[++p].x=x;h[p].y=y;

e[x].push_back(y);

e[y].push_back(x);}}

for(i=1;i<=n;i++) f[i]=find(i);

for(i=1;i<=p;i++){

x=h[i].x;y=h[i].y;

for(j=0;j<e[y].size();j++){

fx=find(x);fy=find(e[y][j]);

if(fx!=fy) f[fx]=fy;}

for(j=0;j<e[x].size();j++){

fx=find(e[x][j]);fy=find(y);

if(fx!=fy) f[fx]=fy;}}

for(i=1;i<=n;i++){

f[i]=find(i);

num[f[i]]++;}

for(i=1;i<=n;i++)

if(num[i]) max++;

cout<<max;

return 0;}

查看更多回复
提交回复