Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 122 Accepted Submission(s): 78
Problem Description
度度熊最近似乎在研究图论。给定一个有 N 个点 (vertex) 以及 M 条边 (edge) 的无向简单图 (undirected simple graph)，此图中保证没有任何圈 (cycle) 存在。
现在你可以对此图依序进行以下的操作：
1. 移除至多 K 条边。
2. 在保持此图是没有圈的无向简单图的条件下，自由的添加边至此图中。
请问最后此图中度数 (degree) 最大的点的度数可以多大呢？
Input
输入的第一行有一个正整数 T，代表接下来有几笔测试资料。
对于每笔测试资料：
第一行有三个整数 N, M, K。
接下来的 M 行每行有两个整数 a 及 b，代表点 a 及 b 之间有一条边。
点的编号由 0 开始至 N?1。
* 0≤K≤M≤2×105
* 1≤N≤2×105
* 0≤a,b<N
* 给定的图保证是没有圈的简单图
* 1≤T≤23
* 至多 2 笔测试资料中的 N>1000
Output
对于每一笔测试资料，请依序各自在一行内输出一个整数，代表按照规定操作后可能出现的最大度数。
Sample Input
2
3 1 1
1 2
8 6 0
1 2
3 1
5 6
4 1
6 4
7 0
Sample Output
2
4
Source
2018 “百度之星”程序设计大赛 - 初赛（B）
Recommend
chendu
没有圈 的简单图，等价于由多颗树 组成的森林。这里用V代表点的数量，E代表边的数量，C代表森林中树的数量。
(取代题目中的N以及M )
K = 0的case
不妨先化简一下题目，在 K = 0的状态下要达到degree最大化，可以贪心的把森林中所有树各自接一条边到已知degree最大的点上。答案是C + 已知最大的 degree - 1。
K ≥ 0的case
回到原题，题目中规定一定要在添加边之前把拔边的操作作完，但是实际上任意调换添加边以及拔掉边的顺序不会影响最后的结果。考虑贪心添加完边的树，可以多拔掉一条边再重新接上的效果等价于把答案+1，要注意的是如果答案已经到达最大值V ? 1的话，那拔边再接上并不会影响答案。所以答案为min(V - 1, K + C + 已知最大的 degree - 1)。
树的数量C = V - E
由于给定的图是面数(face) 为 11的平面图(planar graph)，所以根据平面图的公式V ? E + F = C + 1整理后C = V ? E。另外一个证明：图中每个connected component都是由树所组成，也就是说每个component中边数会是点数- 1，直接可推得C = V - E。
有了 C = V - E后，答案就变成min(V - 1, K + V - E + 已知最大的 degree - 1)。也就是，我们其实不用真正的写出计算connected component的算法，只要统计degree最大的点有多大就可以计算出答案了。
整体时间复杂度为 O ( V )，注意这题中有O ( V ) = O ( E )。
#include<bits/stdc++.h>
using namespace std;
const int N = 15;
const int inf = 1000000000;
int n,m,num,T,k,in[200050],ans,a,b;
int main()
{scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++) in[i]=0;for(int i=1;i<=m;i++){scanf("%d%d",&a,&b);a++,b++;in[a]++;in[b]++;}num=0;for(int i=1;i<=n;i++){num=max(num,in[i]);}ans=m-num-k;ans=max(0,ans);printf("%d\n",n-1-ans);}
}