题目描述

看题

样例

看题

此题是最基础的并查集题型

注释讲解较为详尽，注意使用cin会爆

C++ 代码

#include <cstdio>
#include <iostream>
#define MAXN 20010
using namespace std;
/*
主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：
合并（Union）：把两个不相交的集合合并为一个集合。
查询（Find）：查询两个元素是否在同一个集合中。
*/ 
//rank记录对应树的深度 
int fa[MAXN], r[MAXN];

//初始化，每个元素父亲为自己，深度为1 
inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        r[i] = 1;
    }
}

//查询，如果x是自己的父亲，那就返回
//否则递归查找x的父亲进行返回 
int find(int x)
{
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}

//合并，找到i,j 的父亲然后进行连接即可
//提高效率，进行路径压缩，这里使用按秩合并的方法
//可以使用多个元素指向一个父亲--菊花状
inline void merge(int i, int j)
{
    int x = find(i), y = find(j);
    //深度大的作为深度小的的父亲 
    if (r[x] <= r[y])
        fa[x] = y;
    else
        fa[y] = x;
    //深度相同合并会导致深度加1 
    if (r[x] == r[y] && x != y)
        r[y]++;
}
int main()
{
    /*
    第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。
    以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有亲戚关系。
    接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。   
    */ 
    int n, m, p, x, y;    //x, y为询问的两个人 
    scanf("%d%d", &n, &m);
    init(n);              //初始化 

    //有亲戚关系的进行合并 
    for (int i = 0; i < m; ++i)
    {
        scanf("%d%d", &x, &y);
        merge(x, y);
    }

    scanf("%d", &p);
    //两个人找到了相同的父亲，那么就有亲戚关系 
    for (int i = 0; i < p; ++i)
    {
        scanf("%d%d", &x, &y);
        printf("%s\n", find(x) == find(y) ? "Yes" : "No");
    }
    return 0;
}