PAT甲级备考——并查集

• 题目
• • 【1107】并查集
  • 【114】并查集

PAT (Advanced Level) Practice

【1107】并查集
【1114】 并查集
【1118】并查集（）

并查集知识点参考：https://zhuanlan.zhihu.com/p/29035169

1107 Social Clusters (30 分)
题⽬⼤意：有n个⼈，每个⼈喜欢k个活动，如果两个⼈有任意⼀个活动相同，就称为他们处于同⼀个社交⽹络。求这n个⼈⼀共形成了多少个社交⽹络。

#include
#include
#include
using namespace std;

int N;
vector fa, node_rank;
vector hobbies[1005];

// 初始化，每个节点的父节点是自身，每个节点目前的秩为1，即以该节点为父节点的子树深度为1
inline void init(){
    for(int i=1; i<=N; i++){
        fa[i] = i;
        node_rank[i] = 1;
    }
}
// 根据下标i，找到它的父亲根节点；迭代赋值
int find(int i){
    if(fa[i] == i) return i;
    else{
        fa[i] = find(fa[i]);
        return fa[i];
    }
}
// 合并两个子树a和b，先分别找到a和b的最深的根节点，将rank较小的树合并到rank较大的树下面，为了减少查找难度；
// 如果两个树一样大，则合并，并将父子树的rank值加1
void merge(int a, int b){
    int x = find(a), y = find(b);
    if(node_rank[x] >= node_rank[y]){
        fa[y] = x;
    }else if(node_rank[x] < node_rank[y]){
        fa[x] = y;
    }
    if(node_rank[x] == node_rank[y])
        node_rank[x]++;
}
bool cmp(int a, int b){
    return a>b;
}
int main(){
    
    // 1. 初始化
    cin>>N;
    fa.resize(N+1);
    node_rank.resize(N+1);
    init();
    
    // 2.读入每个人hobbies，根据hobby来合并
    int k, h;
    for(int i=1; i<=N; i++){
        scanf("%d:",&k); // 每个人有k个hobby
        while(k--){
            scanf("%d",&h);
            if(hobbies[h].size()!=0){ // 如果已经有人喜欢第h个hobby了，则将新人i合并到这个hobby的第一个人的子树下
                merge(hobbies[h][0], i);
            }
            hobbies[h].push_back(i); // 第h个hobby中加入新人i
        }
    }
    
    // 3. 统计多少组人
    int group_num = 0;
    vector groups(N+1);
    for(int i=1; i<=N; i++)
        groups[find(i)]++; // 找到每个人的根节点，相同的根节点意味着是同一组人，则该节点对应的人数++
    for(int i=1; i<=N; i++)
        if(groups[i]!=0) group_num++; // 如果某个根节点下有人则组数++
    
    sort(groups.begin(), groups.end(), cmp); //  groups内部按照人数倒叙排列
    
    // 4. 输出
    cout<
        printf("%d%s", groups[i], i==group_num-1?"n":" ");
    }
    
    return 0;
}

题⽬⼤意：给定每个⼈的家庭成员和其⾃⼰名下的房产，请你统计出每个家庭的⼈⼝数、⼈均房产⾯积及房产套数。⾸先在第⼀⾏输出家庭个数（所有有亲属关系的⼈都属于同⼀个家庭）。随后按下列
格式输出每个家庭的信息：家庭成员的最⼩编号 家庭⼈⼝数 ⼈均房产套数 ⼈均房产⾯积。其中⼈均值要求保留⼩数点后3

两个数据结构：首先将所有的输入数据保存至data中，数据结构为自定义的person；进而转化成ans输出数组，数据结构为answer；
并查集的常规merge操作在输入阶段进行，且merge操作保障根节点一定是id值最小的人
维护visited数组，所有出现过的人均置为true；
ans数组中，is_root为true的人就是根节点，计算根节点对应的各种平均值

注意：
这里所有的亲属关系不区分爸爸妈妈（男女），亲属关系中的父子，在并查集中并不一定是父子，merge规则设定与”输出最小id的人“相适应；
printf(“%04d”, data) 将自动补齐0

#include
#include
#include
#include