1 条题解

  • 0
    @ 2026-2-18 15:44:36
    #include<bits/stdc++.h>
    using namespace std;
    
    // [1] 全局常量:最大人数限制,适配题目n≤5000的范围
    const int MAXN = 5010;
    // [2] 全局数组:并查集父节点数组,存储每个人的父节点编号
    int fa[MAXN];
    // [3] 全局数组:并查集深度数组,用于按秩合并优化,避免树结构退化
    int dep[MAXN];
    
    // [15] 跳转至find函数:带路径压缩,查找节点x所在家族的根节点
    int find(int x)
    {
        // [16] 函数参数x:待查找根节点的人的编号
        if(x != fa[x])
        {
            fa[x] = find(fa[x]); // [17] 路径压缩:直接将当前节点指向根节点,大幅优化后续查询效率
        }
        return fa[x]; // [18] 返回找到的根节点,用于判断两个节点是否属于同一集合
    }
    // [19] find函数注释完成,返回unite函数继续注释
    
    // [12] 跳转至unite函数:按秩合并x和y所在的两个家族集合
    void unite(int x, int y)
    {
        // [13] 函数参数x、y:待合并的两个人的编号
        // [14] 调用find函数查找两人的根节点,跳转至该函数完成注释
        x = find(x);
        y = find(y);
        
        if(x == y) return; // [20] 回到unite函数,两人已属于同一家族,无需重复合并
        
        // [21] 按秩合并逻辑:将深度更小的树合并到深度更大的树下,保持树结构平衡,优化查询效率
        if(dep[x] > dep[y])
        {
            fa[y] = x;
        }
        else if(dep[x] < dep[y])
        {
            fa[x] = y;
        }
        else
        {
            fa[y] = x;
            dep[x]++; // 两棵树深度相同时,合并后根节点的深度+1
        }
    }
    // [22] unite函数注释完成,返回主函数继续注释
    
    // [4] 主函数:程序运行入口
    int main()
    {
        int n, m, p;
        cin >> n >> m >> p; // [5] 读入总人数n、亲戚关系总数m、查询次数p
        
        // [6] 循环初始化并查集,为每个人初始化家族连通状态
        for(int i = 1; i <= n; i++)
        {
            fa[i] = i; // [7] 每个人初始独立为一个家族,父节点设为自身
            dep[i] = 1; // [8] 每个家族的初始树深度设为1
        }
        
        // [9] 循环处理所有m条亲戚关系,合并对应人的连通集合
        for(int i = 1; i <= m; i++)
        {
            int Mi, Mj;
            cin >> Mi >> Mj; // [10] 读入有亲戚关系的两个人的编号
            // [11] 调用unite函数合并两人所在的家族,跳转至该函数完成注释
            unite(Mi, Mj);
        }
        
        // [22] 回到主函数,所有亲戚关系处理完成
        // [23] 循环处理p次亲戚关系查询
        for(int i = 1; i <= p; i++)
        {
            int Pi, Pj;
            cin >> Pi >> Pj; // [24] 读入待查询的两个人的编号
            // [25] 调用已注释的find函数,判断两人是否属于同一连通集合
            if(find(Pi) == find(Pj))
            {
                cout << "Yes" << endl; // [26] 根节点相同,具有亲戚关系,输出Yes
            }
            else
            {
                cout << "No" << endl; // [27] 根节点不同,无亲戚关系,输出No
            }
        }
        
        return 0;
    }
    
    
    • 1

    信息

    ID
    1364
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者