1001-degree

题目：

degree

Accepts: 1581

Submissions: 3485

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)
Problem Description

度度熊最近似乎在研究图论。给定一个有

现在你可以对此图依序进行以下的操作：

移除至多

在保持此图是没有圈的无向简单图的条件下，自由的添加边至此图中。

请问最后此图中度数 (degree) 最大的点的度数可以多大呢？

Input

输入的第一行有一个正整数

对于每笔测试资料：第一行有三个整数

$10^50≤K≤M≤2×105$

$10^51≤N≤2×105$

给定的图保证是没有圈的简单图

至多

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

思路：

设该简单图的联通块数（通过并查集计算出）为linkNum，最大度数的点的度数为mxDegree,那么答案就是(mxDegree+linkNum-1+k), 但由于该图没有圈，那么就是说明该图是树，而树的最大度数是n-1 (n为点数)，所以答案不能大于n-1,那么 ans = min( mxDegree+linkNum-1+k ,n-1);

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 2e5+20;

int pre[MAXN],degree[MAXN];
int vis[MAXN];

int find(int x){
    if(pre[x]==x)return x;
    else{
        return pre[x] = find(pre[x]);
    }
}

void join(int x,int y){
    int fx = find(x);
    int fy = find(y);
    if(fx!=fy){
        pre[fx] = fy;
    }
}


void init(int n){
    memset(degree, 0, sizeof(degree));
    memset(vis, 0, sizeof(vis));
    for(int i=0;i<=n;i++){
        pre[i] = i;
    }
}


int main()
{
    int n, m, k,t;
    scanf("%d", &t);
    while(t--){
        scanf("%d%d%d", &n, &m, &k);
        init(n);
        for(int i=1;i<=m;i++){
            int a, b;
            scanf("%d%d", &a, &b);
            join(a, b);
            degree[a]++;
            degree[b]++;
        }
        /// 计算联通块数目
        int linkNum = 0;
        for(int i=0;i<n;i++){
            if(!vis[find(i)]){
                linkNum++;
                vis[find(i)]=1;
            }
        }
        /// 找出最大度数
        int mxDegree = 0;
        for(int i=0;i<n;i++){
            mxDegree = max(mxDegree, degree[i]);
        }

        int ans = (mxDegree+linkNum-1+k);
        if(ans>n-1) ans = n-1;  ///树的最大度数是 n-1
        printf("%d
", ans);

    }



    return 0;
}