蒟蒻本人受大佬题解启发，特来分享自己对题的理解，大佬题解链接->https://blog.csdn.net/xianqiuyigedao/article/details/124242567?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522171341224516800186552691%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=171341224516800186552691&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-124242567-null-null.142^v100^pc_search_result_base8&utm_term=L2-007%20%E5%AE%B6%E5%BA%AD%E6%88%BF%E4%BA%A7&spm=1018.2226.3001.4187

题目描述

输入n，表示有n行，第i行 输入一个字符串表示这个人特有的仅4位数的编号，接着输入2个字符串表示其父母的编号，如果编号为-1则表示离世，接着输入m表示有m个孩子，然后有m个字符串表示孩子的编号，然后就是此人的房子数和面积，输出一共有多少个家庭(只要有共同的父母或孩子都表示一个家庭)，再输出每个家庭的最小编号，成员的数量，人均房产套数，和人均房产面积。

样例

输入
10
6666 5551 5552 1 7777 1 100
1234 5678 9012 1 0002 2 300
8888 -1 -1 0 1 1000
2468 0001 0004 1 2222 1 500
7777 6666 -1 0 2 300
3721 -1 -1 1 2333 2 150
9012 -1 -1 3 1236 1235 1234 1 100
1235 5678 9012 0 1 50
2222 1236 2468 2 6661 6662 1 300
2333 -1 3721 3 6661 6662 6663 1 100
输出
3
8888 1 1.000 1000.000
0001 15 0.600 100.000
5551 4 0.750 100.000

并查集
思路:用并查集来维护他们的关系；大家都知道用并查集来维护数据后，他们都有一个祖先，则遍历0~100000找到一个数i，将i的数全部维护到祖先节点中即可，然后再遍历0~100000，如果i=find(i)表示祖先是它本身，则将祖先节点存入结构体ans中，排序输出即可。

#### C++ 代码

#include<bits/stdc++.h>
#define ed '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
using namespace std;
const int mod = 1e9 + 7;
const int g = 1e6 + 10;
bool bf[g];//将出现的编号标记，以防止没有出现的编号被更新。
int f[g];
int find(int x)
{
    if (f[x] != x)f[x] = find(f[x]);
    return f[x];
}
void add(int x, int y)
{
    f[find(x)] = find(y);
}
struct pp//以结构体来存数据
{
    int id=100000;
    int num = 0;
    int house = 0;
    int sq = 0;
}arr[g];
struct pt//再创建一个结构体存答案
{
    int id ;
    int num;
    double fang;
    double src;
    bool operator<(const pt& v)const//根据题要求，需要将人均房面积降序排列，如果相同则编号升序排列
    {
        if (src == v.src)return id < v.id;
        else return src > v.src;
    }
}ans[g];
void solve()
{
    int n = 0; cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int c=0; cin >> c;
        int f1 = 0, f2 = 0;
        cin >> f1 >> f2;
        if (f1 != -1)bf[f1] = 1, add(c, f1);//如果存在，则并+标记
        if (f2 != -1)bf[f2] = 1, add(c, f2);
        bf[c] = 1;//标记标号c存在

        int k = 0; cin >> k;
        for (int i = 1; i <= k; i++)
        {
            int son = 0; cin >> son;
            bf[son] = 1;//标记编号son存在
            add(c, son);
        }
        int res = 0, src = 0;
        cin >> res >> src;
        arr[c].id = c;
        arr[c].house = res;
        arr[c].sq = src;
    }

    for (int i = 0; i < 100000; i++)
    {
        if (bf[i])
        {
            int fa = find(i);
            arr[fa].num++;
            if (fa == i)continue;//祖先是它本身
            arr[fa].id = min(arr[fa].id, i);
            arr[fa].house += arr[i].house;
            arr[fa].sq += arr[i].sq;
        }
    }
    int cnt = 0;
    for (int i = 0; i < 100000; i++)
    {

        if (find(i) == i && bf[i] == 1)//将祖先的数据存入结构体ans中
        {
            cnt++;//因为我们已经把数据都维护在了祖先节点，所以有多少个祖先节点就有多少个家庭
            ans[i].id = arr[i].id;
            ans[i].num = arr[i].num;
            ans[i].fang = arr[i].house * 1.0 / arr[i].num;
            ans[i].src = arr[i].sq * 1.0 / arr[i].num;

        }
    }

    sort(ans , ans + 100000);//排序

    cout << cnt << ed;
    for (int i = 0; i < 100000; i++)
    {
        if (ans[i].fang > 0&&ans[i].num>0)
        {
            cout << setw(4) << setfill('0') << ans[i].id << " ";//注意补前导0
            cout << ans[i].num << " ";
            printf("%0.3lf %0.3lf\n", ans[i].fang,ans[i].src);      
        }
    }
}
signed main()
{
    for (int i = 0; i < 100000; i++)f[i] = i;//初始化


    int t = 1;

    //cin>>t;

    while (t--)
    {
        solve();
    }



    return 0;
}