技巧

可以不用一下代码初始化与找根

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

int getf(int x)
{
    if(f[x] == x)
        return x;
    return f[x] = getf(f[x]);
}

简化后

int getf(int x)
{
    if(f[x]!=0 && f[x]!=x)
        return f[x] = getf(f[x]);
    return x;
}

原理

以递归压缩路径———getf
合并路径——将节点编号变为根节点编号

根相同,则在同一个子集

模版 并查集

#include <cstdio>
using namespace std;
int getf(int);
void merge(int, int);
inline int fread();
int n, m, f[20002] = {}, q;
int main()
{
	n = fread();
	m = fread();
	int a, b;
	for(int i=1; i<=m; ++i)
	{
		a = fread();
		b = fread();
		merge(a, b);
	}
	q = fread();
	for(int i=1; i<=q; ++i)
	{
		a = fread();
		b = fread();
		int t1 = getf(a), t2 = getf(b);
		if(t1 == t2)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}
int getf(int x)
{
	if(f[x]!=x && f[x]!=0)
        return f[x] = getf(f[x]);
    return x;
}
void merge(int v, int u) 
{
	int t1, t2;
	t1 = getf(v);
	t2 = getf(u);
	if(t1 != t2)
		f[t2] = t1;
	return;
}
inline int fread()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}