Problem Description

度度熊最近似乎在研究圖論。給定一個有 N 個點 (vertex) 以及 M 條邊 (edge) 的無向簡單圖 (undirected simple graph)，此圖中保證沒有任何圈 (cycle) 存在。

現在你可以對此圖依序進行以下的操作：

移除至多 K 條邊。
在保持此圖是沒有圈的無向簡單圖的條件下，自由的添加邊至此圖中。
請問最后此圖中度數 (degree) 最大的點的度數可以多大呢？

Input

輸入的第一行有一個正整數 T，代表接下來有幾筆測試資料。

對于每筆測試資料： 第一行有三個整數 N, M, K。 接下來的 M 行每行有兩個整數 a 及 b，代表點 a 及 b 之間有一條邊。 點的編號由 0 開始至 N-1。
0≤K≤M≤2×1050≤K≤M≤2×105??
1≤N≤2×1051≤N≤2×105??
0≤a,b<N0≤a,b<N
給定的圖保證是沒有圈的簡單圖1≤T≤231≤T≤23
至多 2 筆測試資料中的 N>1000N>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

Solution

其實題目大意就是給你一個森林，可以從中刪去至多k條邊，然后添加任意條邊，但保證還是一個森林或一顆樹，使得一個點的度數最大，讓你求這個最大的度數。
先考慮不刪邊的情況，我們可以發現如果不刪邊，那么它的答案就是這n個點中度數最大的點的度數加上森林的個數再減一，減一是減去當前的這顆樹。就相當于從每顆樹都向這個最大度數的點所在的樹連了一條邊。之后我們考慮刪邊的情況，如果要刪邊，那么也就是相當于將除了這個最大度數的點向其他點連的邊，其他邊都要盡量刪去，然后再盡可能多的向這個最大度數的點連一條邊，這樣就能保證在不損失最大度數的情況下再讓答案更優。綜上，答案就是度數最大的點的度數+森林的個數-1+min（m-度數最大的點的度數,k）。

---

作者：zsjzliziyang
QQ:1634151125
轉載及修改請注明
本文地址:https://blog.csdn.net/zsjzliziyang/article/details/81607176

總結

以上是生活随笔為你收集整理的【2018百度之星程序设计大赛初赛】degree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。