题目描述
简单的并查集模拟题,需要用到路径压缩
一共分为三步:
初始、查找、连接
样例
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e4+10;
int n,m,q;
int s[N];
void init()
{
for(int i=1;i<=n;i++)
{
s[i]=i;
}
}
int find_set(int x)
{
//这样子未优化,可能会导致树的高度过大
//return x==s[x]?x:find_set(s[x]);
if(x!=s[x])s[x]=find_set(s[x]);
return s[x];
}
void union_set(int a,int b)
{
a=find_set(a);
b=find_set(b);
s[a]=b;
}
void test(int c,int d)
{
//s[c]!=s[d],因为有可能s[1]==3,s[2]==3而s[3]==4,s[4]==4的情况出现
if(find_set(c)==find_set(d))
printf("Yes\n");
else
printf("No\n");
}
int main()
{
scanf("%d%d", &n, &m);
init();
while (m -- ){
int a,b;
scanf("%d%d", &a, &b);
union_set(a,b);
}
scanf("%d", &q);
while(q--){
int c,d;
scanf("%d%d", &c, &d);
test(c,d);
}
}