【并查集】最大数量

题目

4866. 最大数量 - AcWing题库

---

一个无向图有 $n$ 个点，编号 $1 \sim n$ 。

这些点之间没有任何边。

给定 $d$ 个需求，编号 $1 \sim d$ 。

其中，第 $i$ 个需求是让点 $x_i$ 和点 $y_i$ 连通。

需求可能存在重复。

在本题中，你需要依次解决 $d$ 个问题，编号 $1 \sim d$ 。

其中，第 $i$ 个问题是，请你在图中添加恰好 $i$ 条无向边（不能添加重边和自环），使得：

1. 前 $i$ 个需求都得到满足。
2. 所有点的度的最大值尽可能大。

对于每个问题，你不需要输出具体方案，你只需要输出度的最大可能值。

注意：

1. 如果点 $a$ 和点 $b$ 之间存在路径，则称点 $a$ 和点 $b$ 连通。
2. 图中与点 $a$ 关联的边数，称为点 $a$ 的度。
3. $d$ 个问题之间是相互独立的，每个问题的答案都必须独立计算。

输入格式

第一行包含两个整数 $n,d$ 。

接下来 $d$ 行，其中第 $i$ 行包含两个整数 $x_i,y_i$ ，表示第 $i$ 个需求是让点 $x_i$ 和点 $y_i$ 连通。

输出格式

共 $d$ 行，其中第 $i$ 行输出第 $i$ 个问题中，度的最大可能值。

数据范围

前三个测试点满足， $2 \le n \le 10$ 。
所有测试点满足， $2 \le n \le 1000$ ， $1 \le d \le n-1$ ， $1 \le x_i,y_i \le n$ ， $x_i \neq y_i$ 。

输入样例1：

7 6
1 2
3 4
2 4
7 6
6 5
1 7

输出样例1：

1
1
3
3
3
6

输入样例2：

10 8
1 2
2 3
3 4
1 4
6 7
8 9
8 10
1 4

输出样例2：

1
2
3
4
5
5
6
8

解题

方法一：并查集

思路

要在无重边、自环的无向图中使顶点的度的最大值尽可能大，这样图应该形如：

此时该连通图中顶点的度的最大值为顶点的数量-1 ，这样的图恰好可以用维护每个集合大小的基于路径压缩的并查集来维护其连通关系与每个连通子图的顶点数量。

题目中要求在第 $i$ 个问题时在图中添加恰好 $i$ 条无向边使前 $i$ 个需求被满足，而这 $i$ 条边不一定全部要用来连接需求节点，比如已经存在 $A \leftrightarrow B, B \leftrightarrow C$ ，那么当第 $i$ 个需求是 $A \leftrightarrow C$ 时就不需要连接 $A, C$ ，因为 $A, C$ 在完成之前需求时已经顺便完成了，那么这第 $i$ 条边就可以用来把最大的两个连通子图连接起来，这样以来图中顶点的度的最大值就变为原来最大的两个连通子图中的顶点度的最大值之和+1 ，如图：

综上，具体做法是：

使用维护集合大小的、路径压缩的并查集来维护图中连通关系与每个连通子图的顶点数量。

遍历每个需求，对于第 $i$ 个需求 $x_i \leftrightarrow y_i$ ：

• 先检查 $x_i$ 与 $y_i$ 是否在一个连通子图中：
  • 如果在，就把第 $i$ 条边先留空出来（cnt++）。
  • 否则把第 $i$ 条边用来连接 $x_i, y_i$ （union(x, y)）。
• 然后枚举每一个节点，把并查集中每个不同集合的顶点数量放入列表（sizeLst）中（并查集中 v == find(v) 的节点被看作是它所在集合的根节点，该集合的大小为 sizes[v]）。
• 接下来把 sizeLst 按照从大到小的顺序排序。
• 最后把最大的 cnt+1 个集合合并，此时集合中的顶点数量-1即为对于第 $i$ 个需求来说度的最大可能值。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int[] roots, sizes;
    
    static int find(int x) {
        return roots[x] == x ? x : (roots[x] = find(roots[x]));
    }
    
    static void union(int p, int q) {
        p = find(p);
        q = find(q);
        roots[p] = q;
        sizes[q] += sizes[p];
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int d = (int) in.nval;
        roots = new int[n + 1];
        sizes = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            roots[i] = i;
            sizes[i] = 1;
        }
        int cnt = 1;
        for (int i = 1; i <= d; ++i) {
            in.nextToken();
            int x = (int) in.nval;
            in.nextToken();
            int y = (int) in.nval;
            if (find(x) != find(y)) union(x, y);
            else ++cnt;
            List<Integer> sizeLst = new ArrayList<>();
            for (int j = 1; j <= n; ++j) {
                if (find(j) == j) sizeLst.add(sizes[find(j)]);
            }
            sizeLst.sort((a, b) -> b - a);
            int j = 0, sum = 0;
            for (int sz : sizeLst) {
                sum += sz;
                if (++j == cnt) break;
            }
            System.out.println(sum - 1);
        }
    }
}