并查集+路径压缩

并查集 时间复杂度查O(1) + 并O（n） 轻松秒杀

注意输入的数据是分开的 我就是被坑了

没什么好说的 看代码 模板题

update : 本题输入数据量巨大 输入请用scanf

Code:

#include <iostream>
#include <algorithm>
#define int long long //个人习惯
using namespace std;
int f[100010];
int n , m , p;
int find_fa(int x)  //查
{
    while (x != f[x]) x = f[x] = f[f[x]]; // 路径压缩 模板记住就行
    return x;
}
signed main() //signed 同 int
{
    scanf("%lld%lld" , &n , &m);
    for (int i = 1 ; i <= n ; i ++ ) f[i] = i;
    for (int i = 1 ; i <= m ; i ++ )
    {
        int temp1 , temp2;
        scanf("%lld%lld",&temp1 , &temp2);
        f[find_fa(temp2)] = find_fa(temp1); //并
    }
    scanf("%lld", &p);
    for (int i = 1 ; i <= p ; i ++ )
    {
        int temp1 , temp2;
        scanf("%lld%lld",&temp1 , &temp2);
        if (find_fa(temp2) == find_fa(temp1))
            printf ("Yes\n");
        else
            printf ("No\n");
    }
    return 0;
}

很简单的模板题 祝刷到的帅哥美女全都ac ！