TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

76.2% (16/21)

Description

金氏運動公司打算舉辦一場馬拉松比賽,為了締造亮眼的完成比賽時間,金氏運動公司打算選擇性地邀請選手參賽。分析過往的數據資料,金氏運動公司觀察到以下二個現象:
(a) 對於任何一位選手,如果愈多他的朋友參賽,則他就能跑得愈快,所以傾向於找一群選手使得彼此互相認識的情況很多。因為認識是雙向的,如果$P$ 認識$Q$,則$Q$ 認識$P$。所以當我們說$P$ 認識$Q$ 時,等同於表示$P$、$Q$ 兩位互相認識。
(b) 如果參賽的選手當中,存在兩位選手$P$ 和$Q$ 彼此不認識,而且在參賽的選手當中無法找到$t$ 位選手$S_1, S_2,\ldots S_t$ ($t$ 為任意大於0 的整數),使得$P$ 認識$S_1$,$S_1$ 認識$S2$,…,$S_{t-1}$ 認識$S_t$,$S_t$ 認識$Q$,則比賽將會有嚴重的惡性競爭,所以需要避免這樣的狀況。

現在金氏運動公司手上有一份$N$ 位選手的名單以及一份顯示這$N$ 位選手彼此之間是否認識的表單,現在的任務是從這$N$ 位選手找出選手的子集合$S = \{P_1, P_2, \ldots, P_{\lvert S \rvert} \}$,使得$S$ 沒有惡性競爭的狀況,而且讓以下影響因子$F(S)$得到最大化,這影響因子的設計除了讓每位選手都認識夠多的參賽者,也兼顧了不讓參賽人數過少。
$$F(S) = \lvert S \rvert \min\limits_{1\leq i \leq \lvert S \rvert} D_i$$
其中$D_i$ 表示選手$P_i$ 所認識的人當中,有多少人在子集合$S$ 裡面。 在以下這個4 位選手的例子中,選 $S = \{2, 3, 4\}$ 比其他的選法有更高的$F(S)$。

Input Format

每一組測試資料有兩列, 其中第一列有兩個正整數$N$ 和$M (1\leq M \leq \frac{N(N-1)}{2})$,第二列有$M$ 對正整數$X_1 Y_1 X_2 Y_2 \ldots X_M Y_M$,代表選手$X_i$ 認識選手$Y_i $ ($1\leq i \leq M$ 且$1\leq Xi < Yi \leq N$)。

Output Format

對於每組測試資料,輸出最大的$F(S)$。$F(S)$這數字需獨自佔一列。

Sample Input

Sample Input #1
4 5
1 2 2 3 3 4 4 1 2 4

Sample Input #2
4 4
1 2 2 3 3 4 2 4

Sample Input #3
6 6
1 3 1 2 2 3 4 5 5 6 4 6

Sample Output

Sample Output #1
8

Sample Output #2
6

Sample Output #3
6

Hints

本題共有三個子題,每一子題可有多筆測試資料:
第一子題的測試資料中$N \leq 100$,全部解出可獲19 分;
第二子題的測試資料中$N \leq 500$,全部解出可獲38 分;
第三子題的測試資料中$N \leq 5000$,全部解出可獲43 分。

Problem Source

106學年度高級中學資訊學科能力競賽決賽 程式設計試題第五題

Subtasks

For Testdata: 0 ~ 9, Score: 19
For Testdata: 10 ~ 19, Score: 38
For Testdata: 20 ~ 29, Score: 43
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 4000 524288 65536
1 4000 524288 65536
2 4000 524288 65536
3 4000 524288 65536
4 4000 524288 65536
5 4000 524288 65536
6 4000 524288 65536
7 4000 524288 65536
8 4000 524288 65536
9 4000 524288 65536
10 4000 524288 65536
11 4000 524288 65536
12 4000 524288 65536
13 4000 524288 65536
14 4000 524288 65536
15 4000 524288 65536
16 4000 524288 65536
17 4000 524288 65536
18 4000 524288 65536
19 4000 524288 65536
20 4000 524288 65536
21 4000 524288 65536
22 4000 524288 65536
23 4000 524288 65536
24 4000 524288 65536
25 4000 524288 65536
26 4000 524288 65536
27 4000 524288 65536
28 4000 524288 65536
29 4000 524288 65536