第10章 并查集

1013. Battle Over Cities

笔记

• 题目求的是：删除一个顶点后，剩余的连通块至少需要再添加多少条边才能连通？
• 假设剩余的连通块的个数是$k$，则至少需要$k-1$条边（类似树），因此需要求剩余连通块的个数

• 可通过DFS找到所有连通块，但复杂度较高；并查集也可以间接获取连通块的个数，假设顶点个数是$n$

  • 删除一个顶点后剩余$n-1$个顶点，至多有$n-1$个连通块，开始把它们都看做孤立点

  • 遍历所有边

    • 如果边上的点都不是被删除的顶点，且各自的并查集根节点不是同一个，则合并这两个点，连通块个数-1
    • 如果边上的点包含被删除的顶点，则跳过该条边

  • 最后即可得到连通块个数

• 注意本题边的个数最大可能有$500000$个，因此需要用scanf和printf

#include <iostream>
using namespace std;
const int N = 1010, M = 500010;
int n, p[N];

struct Edge {
    int u, v;
} e[M];

void init() {
    for (int i = 1; i <= n; i++)
        p[i] = i;
}

int find(int u) {
    if (p[u] != u) p[u] = find(p[u]);
    return p[u];
}

int main() {
    int m, k;
    scanf("%d%d%d", &n, &m, &k);

    for (int i = 0; i < m; i++)
        scanf("%d%d", &e[i].u, &e[i].v);

    int x;
    while(k--) {
        scanf("%d", &x);

        init();     // 初始化并查集

        int cnt = n - 1;        // 初始连通块个数
        for (int i = 0; i < m; i++) {
            int u = e[i].u, v = e[i].v;
            if (u != x && v != x) {
                int pu = find(u), pv = find(v);
                if (pu != pv) {
                    // 不在一个连通块
                    p[pu] = pv;     // 合并
                    cnt--;          // 连通块个数-1
                }
            }
        }

        printf("%d\n", cnt - 1);        // 至少需要连通块个数-1条边才能连通
    }

    return 0;
}

1114. Family Property

笔记

• 这题难点在于理清题意（本质是模拟题）
  • 假定所有人都有一个唯一的ID，然后题目给出所有人的家庭成员情况——自己、父母和所有孩子的ID，自己的房产总数，自己的房产总面积
  • 不仅自己有房产，父母和孩子可能也有房产，因此题目想让我们把这些属于同一个家族的房产合并在一起，由于有多种方案，因此取编号最小的作为代表结点（根结点）
  • 按指定次序（重载<）输出各个家族的代表id，总人数、平均房产数、平均房产面积

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;
struct Edge {
    int u, v;
} e[N];

struct Family {
    int id, n;
    int sets_n, total_area;

    bool operator< (const Family& f) const {
        // total_area / n > f.total_area / f.n  
        if (total_area * f.n != f.total_area * n)
            return total_area * f.n > f.total_area * n;  // 人均房产面积降序
        else return id < f.id;          // ID升序
    }

} family[N];

int cnt[N];                         // 第i个元素所在集合（家庭）的元素个数
int sets_n[N], total_area[N];       // 房产总数，房产面积总数
bool st[N];                         // 标记是否是人

int p[N];           // 并查集
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    int n;
    scanf("%d", &n);

    // 1.读入数据
    int id, father, mother, k, child;
    int m = 0;
    while(n--) {
        scanf("%d%d%d%d", &id, &father, &mother, &k);
        st[id] = true;      // 标记是人
        if (father != -1) e[m++] = {id, father};     
        if (mother != -1) e[m++] = {id, mother};
        while(k--) {
            scanf("%d", &child);
            e[m++] = {id, child};
        }
        scanf("%d%d", &sets_n[id], &total_area[id]);
    }


    // 2.汇总数据
    // 初始化并查集
    for (int i = 0; i < N; i++) {
        p[i] = i;
        cnt[i] = 1;
    }

    for (int i = 0; i < m; i++) { 
        int u = e[i].u, v = e[i].v;
        st[u] = st[v] = true;           // 标记是人
        int pu = find(u), pv = find(v);
        if (pu != pv) {
            if (pu > pv) swap(pu, pv);  // 保证pu是编号小的
            p[pv] = pu;                 // 编号小的做根结点
            cnt[pu] += cnt[pv];         // 更新以pu为根结点的树结点个数（家族人数）
            sets_n[pu] += sets_n[pv];   // 更新房产总数
            total_area[pu] += total_area[pv];   // 更新房产面积总数
        }
    }

    n = 0;      // 家庭总数
    for (int i = 0; i < N; i++)
        if (st[i] && p[i] == i)
            family[n++] = {i, cnt[i], sets_n[i], total_area[i]};  // 根结点且被标记过是人

    sort(family, family + n);       // 排序       

    printf("%d\n", n);
    for (int i = 0; i < n; i++) { 
        int id = family[i].id, num = family[i].n;
        double avg_sets_n = (double) family[i].sets_n / family[i].n;
        double avg_total_area = (double) family[i].total_area / family[i].n;
        printf("%04d %d %.3lf %.3lf\n", id, num, avg_sets_n, avg_total_area);
    }

    return 0;
}

1118. Birds in Forest

笔记

• 题目解读

  • 假设顶点集$V$有$n$个顶点，即题目中“鸟的个数”
  • $V$可划分成$t$个顶点子集$V_i$，给定$m$顶点子集$V_i$的子集$v_j \subseteq V_i$，，即题目中定义的“照片个数”
  • 问这$m$个子集$\left\{ v_j \right\} $至多属于多少个顶点子集$\left\{ V_i \right\} $，即题目中所定义的“树的个数”，

• 可先把所有顶点看成孤立顶点，每读入一个子集，就用并查集合并这些顶点，让它们属于同一个集合

• 利用关系“顶点个数 - 合并次数 = 连通分量个数”，在这连通分量个数就是树的个数

#include <iostream>
using namespace std;
const int M = 1e4 + 10, K = 12;
int p[M];       // 并查集
int birds[K];
bool st[M];     // 是否存有数据（统计鸟的总数）

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    int n;
    scanf("%d", &n);

    // 初始化并查集
    for (int i = 0; i < M; i++) p[i] = i;

    int k, merge_cnt = 0;
    while(n--) {
        scanf("%d", &k);
        for (int i = 0; i < k; i++) {
            scanf("%d", &birds[i]);
            st[birds[i]] = true;
        }

        // 构造边
        for (int i = 0; i < k - 1; i++) {
            int pa = find(birds[i]), pb = find(birds[i + 1]);
            if (pa != pb) {
                merge_cnt++;    // 合并次数 = 鸟的总数 - 连通分量个数（照片）
                p[pa] = pb;
            }
        }
    }

    int bird_cnt = 0;           // 鸟的总数
    for (int i = 0; i < M; i++)
        bird_cnt += st[i];

    printf("%d %d\n", bird_cnt - merge_cnt, bird_cnt); // 连通分量个数，顶点总数
    int q, a, b;
    scanf("%d", &q);
    while(q--) {
        scanf("%d%d", &a, &b);
        if (find(a) == find(b)) puts("Yes");
        else puts("No");
    }

    return 0;
}

1107. Social Clusters

笔记

• 用并查集完成合并操作，除此之外还需要考虑数据的存储。
• 首先统计每个爱好有哪些人。由于至多有1000个爱好，因此可创建爱好数组vector<int> hobby[M]。hobby[i]是一个变长数组vector<int>，其元素为人的编号，表示这些人有爱好i。
• 创建并查集，每个元素表示人员编号
• 遍历所有爱好，对hobby[i]里所有元素执行集合合并操作
• 根据祖宗结点编号划分集合，统计各集合元素个数
• 把所有集合元素个数降序排序
• 统计非空集合个数并输出
• 降序输出各个集合的元素个数

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1010;     // 最大人数
const int M = 1010;     // 最大爱好数
int n, p[N], cnt[N];
vector<int> hobbies[M];

int find(int u) {
    if (p[u] != u) p[u] = find(p[u]);
    return p[u];
}

int main() {
    scanf("%d", &n);

    // 按爱好分类
    int m, x;
    for (int i = 1; i <= n; i++) {
        scanf("%d: ", &m);
        while(m--) {
            scanf("%d", &x);
            hobbies[x].push_back(i);
        }
    }

    // 初始化并查集
    for (int u = 1; u <= n; u++) p[u] = u;

    // 构建并查集
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j < hobbies[i].size(); j++) {
            int a = hobbies[i][0], b = hobbies[i][j];
            p[find(b)] = find(a);
        }
    }

    // 统计集合元素个数
    for (int i = 1; i <= n; i++)
        cnt[find(i)]++;

    sort(cnt + 1, cnt + n + 1, greater<int>());

    int set_n = 0;
    for (int i = 1; i <= n && cnt[i]; i++) set_n++;
    printf("%d\n", set_n);

    printf("%d", cnt[1]);
    for (int i = 2; i <= set_n; i++)
        printf(" %d", cnt[i]);
    printf("\n");

    return 0;
}