并查集
作者:
RecSys
,
2021-04-17 11:37:43
,
所有人可见
,
阅读 416
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3+5;
int p[N];
int n,m,t;
void init()
{
for(int i=1;i<=n;i++) p[i]=i;
}
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
void u(int x,int y)
{
p[find(y)]=find(x);
}
int main()
{
cin>>n>>m>>t;
init();
while (m -- )
{
int x,y;
cin>>x>>y;
u(x,y);
}
while(t--)
{
int x,y;
cin>>x>>y;
if(find(x)!=find(y)) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
#include<iostream>
using namespace std;
const int N =100010;
int parent[N];
void Build(int n)
{
for(int i=1;i<=n;i++)
parent[i]=i;
}
int Find(int x)
{
if(parent[x]!=x) parent[x]=Find(parent[x]);
return parent[x];
}
void Union(int x,int y)
{
parent[Find(y)]=Find(x);
}
int main()
{
int n,m;
cin>>n>>m;
Build(n);
while(m--)
{
char op[2];
scanf("%s",op);
if(op[0]=='M')
{
int x,y;
cin>>x>>y;
Union(x,y);
}
else
{
int x,y;
cin>>x>>y;
if(Find(x)==Find(y)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}