记录编号	347719	评测结果	AAAAAAAAAAAA
题目名称	亲戚	最终得分	100
用户昵称	诸星真	是否通过	通过
代码语言	C++	运行时间	0.401 s
提交时间	2016-11-13 15:43:47	内存使用	0.97 MiB

#include <cstdio>
 

int i;
#define N 100000
int fa[N+1];




//查找并路径压缩 非递归
int find(int x){
    int t =x;
    while(fa[t] != t) //不停的往上走
        t=fa[t];

    int i = x,j;//路径压缩，再走一便路程，把走过的点都指向根
    while(i != t){
        j= fa[i];
        fa[i] = t; // 把这个点指向根
        i = j;
    }

    return t;
}

int path[N]={0};
int find2(int x){
    int count =0;
    while(x != fa[x]){
        path[++count] = x;
        x = fa[x];
    }

    int i;
    for(i=1;i <= count;i++){ //这里i < count 是因为 path 记录的第 count 的点一定是指向 root 的,所以可以不用到count
        path[i] = x;
    }
    return x;
}


// 查找 递归法 在面对很深的树的时候 效率很低,且可能会崩溃

int  find3(int x)
{
    if( x != fa[x]) 
        fa[x] = find(fa[x]);
    else 
        return fa[x];
}


// 合并
int join(int x,int y)
{ //合并 x, y所在的集合
    int fx = find(x),fy=find(y);
    if( fx != fy)
        fa[fx] = fy;
}


int main()
{
	freopen("relations.in","r",stdin);
	freopen("relations.out","w",stdout);
	int n,m,q;
	int a,b;
	for(i=1;i<=N;i++)
    fa[i]=i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		join(a,b);
	}
	scanf("%d",&q);
	for(i=1;i<=q;i++)
	{
		scanf("%d%d",&a,&b);
		if(find3(a) == find3(b))
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}