1 条题解

  • 0
    @ 2026-2-18 15:38:41
    #include<bits/stdc++.h>
    using namespace std;
    
    // 最大人数限制,适配题目n≤1e5的范围
    const int MAXN = 1e5 + 10;
    // 并查集父节点数组:存储每个人的父节点编号
    int fa[MAXN];
    // 并查集深度数组:用于按秩合并优化,避免树结构退化
    int dep[MAXN];
    
    // 并查集查找函数:带路径压缩,查找节点x所在集合的根节点
    int find(int x)
    {
        if(x != fa[x])
        {
            fa[x] = find(fa[x]); // 路径压缩:直接将节点指向根节点,优化后续查询效率
        }
        return fa[x];
    }
    
    // 并查集合并函数:按秩合并x和y所在的两个集合
    void unite(int x, int y)
    {
        x = find(x);
        y = find(y);
        
        if(x == y) return; // 两人已属于同一家族,无需重复合并
        
        // 按秩合并:将深度更小的树合并到深度更大的树下,保持树结构平衡
        if(dep[x] > dep[y])
        {
            fa[y] = x;
        }
        else if(dep[x] < dep[y])
        {
            fa[x] = y;
        }
        else
        {
            fa[y] = x;
            dep[x]++; // 两棵树深度相同时,合并后根节点深度+1
        }
    }
    
    int main()
    {
        // 关闭输入同步流,加速cin读取,适配m≤1e6的大数据量
        ios::sync_with_stdio(false);
        cin.tie(0);
        
        int n, m;
        cin >> n >> m; // 读入总人数n、亲戚关系总数m
        
        // 初始化并查集:每个人初始独立为一个家族
        for(int i = 1; i <= n; i++)
        {
            fa[i] = i;
            dep[i] = 1;
        }
        
        // 处理所有亲戚关系,合并对应家族
        for(int i = 1; i <= m; i++)
        {
            int x, y;
            cin >> x >> y; // 读入有亲戚关系的两个人的编号
            unite(x, y); // 合并两人所在的家族
        }
        
        // 统计家族总数:即并查集中根节点的数量
        int familyCnt = 0;
        for(int i = 1; i <= n; i++)
        {
            if(find(i) == i) // 节点的根是自身,说明是一个家族的根节点
            {
                familyCnt++;
            }
        }
        
        cout << familyCnt << endl; // 输出最终的家族总数
        return 0;
    }
    
    • 1

    信息

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