最大数量
一个无向图有 $n$ 个点，编号 $1 \sim n$。
这些点之间没有任何边。
给定 $d$ 个需求，编号 $1 \sim d$。
其中，第 $i$ 个需求是让点 $x_i$ 和点 $y_i$ 连通。
需求可能存在重复。
在本题中，你需要依次解决 $d$ 个问题，编号 $1 \sim d$。
其中，第 $i$ 个问题是，请你在图中添加恰好 $i$ 条无向边（不能添加重边和自环），使得：
- 前 $i$ 个需求都得到满足。
- 所有点中度最大的点的度尽可能大。
对于每个问题，你不需要输出具体方案，你只需要输出度的最大可能值。
注意：
- 如果点 $a$ 和点 $b$ 之间存在路径，则称点 $a$ 和点 $b$ 连通。
- 图中与点 $a$ 关联的边数，称为点 $a$ 的度。（如果一个点是一条边的端点，则称这个点和这条边关联）
- $d$ 个问题之间是相互独立的，每个问题的答案都必须独立计算。
输入格式
第一行包含两个整数 $n,d$。
接下来 $d$ 行，其中第 i 行包含两个整数 $x_i,y_i$，表示第 i 个需求是让点 $x_i$ 和点 $y_i$ 连通。
输出格式
共 $d$ 行，其中第 $i$ 行输出第 $i$ 个问题中，度的最大可能值。
数据范围
前三个测试点满足，$2 \leq n \leq 10$。
所有测试点满足，$2 \leq n \leq 1000$，$1 \leq d \leq n−1$，$1 \leq x_i,y_i \leq n$，$x_i \ne 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
解题思路
这题读了半天都不知道在说什么，对于第$i$个问题恰好添加$i$条边，一直不知道是指在第$i$个问题加$i$条边还是之前的问题加起来恰好$i$条边。后面看了题解才知道每个问题都是独立的，每次考虑前$i$个问题就可以了，对于第$i$个问题，可以重新构图，添加$i$条边来满足前$i$个条件。
对于每个询问，要满足$x_i$和$y_i$连通，因此可以用并查集来维护。因此对于前$i$个问题，在添加完$i$条边后就会形成若干个连通块，假设有$m$个连通块，第$i$个连通块的大小为$\text{cnt}_i$。由于每个连通块相互独立，因此在考虑度数的时候分别看每个连通的最大度数。对于第$i$个连通块，我们可以构造一个菊花图，使得某个点的最大度数为$\text{cnt}_i - 1$。
对于前$i$个询问，每个询问最多添加一条边就可以满足需求，因此添加$i$条边是一定可以满足前$i$个需求，有解。但实际上我们不一定要用$i$条边。比如如果$x_i$与$y_i$本身就已经连通了，如果我们再对$x_i$与$y_i$连一条边，实际上就是在该连通块内连一条边，并不能增加最大度数（某个连通块的最大度数都是$\text{cnt}_i - 1$，即连通块内点的个数减$1$）。因此对于多出来的边，我们可以用来连通某两个连通块，这样两个连通块就合并成了一个，新的连通块的某个点的最大度数就是$\text{cnt}_i + \text{cnt}_j - 1$，度数就变大了。
因此对于前$i$个询问，看一下有多少条多余的边，假设为$s$，那么我们可以用这$s$条边来合并$s + 1$个连通块。为了使得得到的度数最大，可以按照连通块从大到小的顺序来合并。
AC代码如下，时间复杂度为$O(n^2 \log {n})$：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int N = 1010;
5
6 int fa[N], cnt[N];
7
8 int find(int x) {
9 return fa[x] == x ? fa[x] : find(fa[x]);
10 }
11
12 int main() {
13 int n, m;
14 scanf("%d %d", &n, &m);
15 for (int i = 1; i <= n; i++) {
16 fa[i] = i;
17 cnt[i] = 1;
18 }
19 int s = 0;
20 vector<int> tmp;
21 for (int i = 1; i <= m; i++) {
22 int x, y;
23 scanf("%d %d", &x, &y);
24 x = find(x), y = find(y);
25 if (x != y) {
26 cnt[x] += cnt[y];
27 fa[y] = x;
28 }
29 else { // x和y已经在同一个连通块，不需要再连边了
30 s++;
31 }
32 tmp.clear();
33 for (int i = 1; i <= n; i++) {
34 if (fa[i] == i) tmp.push_back(cnt[i]);
35 }
36 sort(tmp.begin(), tmp.end(), greater<int>());
37 int ret = 0;
38 for (int i = 0; i < tmp.size() && i < s + 1; i++) { // 选出最大的s+1个连通块进行合并
39 ret += tmp[i];
40 }
41 printf("%d\n", ret - 1); // 最大度数就是构造菊花图，连通块的大小减1
42 }
43
44 return 0;
45 }
日记
这刚好是我的第$300$篇博客，也是我来博客园写博客的第$2$年，回想起当时什么都不会的我，再到现在已经掌握了大部分算法，还蛮多感慨的。我很怀念写博客的这段时间，因为我还蛮喜欢分享一些知识的见解和个人的想法，不过比较糟糕的是并没有很多人访问我的博客，感觉帮助到的人会比较少。不过这也或许说明了我的文字表达能力并不那么的优秀，博文的质量也没那么高，因此还有很多需要学习的地方。
在这两年我学到了很多的数学和算法知识，也更加坚定了对数学和算法的喜爱。不过最近我的状态还蛮糟糕的，一方面不知道有没有机会保研，即使我已经尽我最大的努力，但还是一个概率的问题。另一方面是我找不到适合我的专业。虽说我是计算机专业，但实际上我更想读数学的专业。所以我找了$\text{tcs}$这个方向的专业，但不幸的是国内在这方面的资源十分匮乏，基本都集中在了国内最顶尖的高校，很明显我这种普通人是不可能达到这种高度的。所以我现在的情况还挺矛盾的。未来会怎么样真的很模糊，有很多不确定的因素，这也是我现在总是担心的地方。
但不管怎么样，只要我对数学和算法的热情不减，就一定会继续写博客与网友分享我的知识和见解。
最后放张《魔法少女小圆》的图吧，我很喜欢的一部动漫。话说我写了这么多的博客都没放过二次元的图片。
参考资料
AcWing 4866. 最大数量（AcWing杯 - 周赛）：https://www.acwing.com/video/4638/
标签：度数,连通,最大,int,text,leq,条边,数量 From： https://www.cnblogs.com/onlyblues/p/17167267.html