算法 c++ 数据结构 并查集 Union-find

链接: 合并集合

#include

using namespace std;

const int N =100010;

int p[N];

int find(int x)

{

if(p[x]!=x) p[x]=find(p[x]);

return p[x];

}

int main()

{

int n,m;

scanf("%d%d",&n,&m);

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

while(m--)

{

char op[2];

int a,b;

scanf("%s%d%d",op,&a,&b);

if(*op=='M') p[find(a)]=find(b);

else

{

if(find(a)==find(b)) puts("Yes");

else puts("No");

}

}

return 0;

}

链接:连通块中点的数量

#include

using namespace std;

const int N =100010;

int n,m;

int p[N],cnt[N];

int find(int x)

{

if(p[x]!=x) p[x]=find(p[x]);

return p[x];

}

int main()

{

cin>>n>>m;

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

{

p[i]=i;

cnt[i]=1;

}

while(m--)

{

string op;

int a,b;

cin>>op;

if(op=="C")

{

cin>>a>>b;

a=find(a),b=find(b);

if(a!=b)

{

p[a]=b;

cnt[b]+=cnt[a];

}

}

else if(op=="Q1")

{

cin>>a>>b;

if(find(a)==find(b)) puts("Yes");

else puts("No");

}

else

{

cin>>a;

cout<

}

}

return 0;

}

好文阅读

 您阅读本篇文章共花了：