在圖論領域中,對於一個無向圖而言,滿足兩兩之間有邊連接的頂點集合,被稱為該無向圖的團。團是圖論中的基本概念之一,用在很多數學問題以及圖的構造上。計算機科學中也有
對它的研究,儘管在一個圖中尋找給定大小的團達到了NP 完全的難度,人們還是研究過很多尋找團的算法。
即使尋找團的問題是如此的困難,但傳說中,某個小島舉行的ACM-ICPC 區域賽卻常常有最大團問題。即給定一張無向圖,找出一個頂點數最多的團。
身為一個專業的競賽選手,艾迪準備了最大團的codebook,以應付某小島賽區的題目。但今年該賽區居然不出最大團問題了,反而出了一道最大不團問題!即找一個最大的頂點集合,使得他並不是一個團。
由於艾迪已經驚慌失措了,你能夠幫助他解決這個問題嗎?
測試資料第一行有兩個數字$N, M$,分別表示圖的頂點個數以及邊數。
接下來$M$ 行,每行包含兩個數字$u_i, v_i$,表示$u_i$ 與$v_i$ 之間有一條邊。
輸出一個數字於一行,表示最大不團的頂點個數。
2017 NPSC高中組決賽
No. | Testdata Range | Score |
---|---|---|
1 | 0~81 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 262144 | 262144 | |
1 | 1000 | 262144 | 262144 | |
2 | 1000 | 262144 | 262144 | |
3 | 1000 | 262144 | 262144 | |
4 | 1000 | 262144 | 262144 | |
5 | 1000 | 262144 | 262144 | |
6 | 1000 | 262144 | 262144 | |
7 | 1000 | 262144 | 262144 | |
8 | 1000 | 262144 | 262144 | |
9 | 1000 | 262144 | 262144 | |
10 | 1000 | 262144 | 262144 | |
11 | 1000 | 262144 | 262144 | |
12 | 1000 | 262144 | 262144 | |
13 | 1000 | 262144 | 262144 | |
14 | 1000 | 262144 | 262144 | |
15 | 1000 | 262144 | 262144 | |
16 | 1000 | 262144 | 262144 | |
17 | 1000 | 262144 | 262144 | |
18 | 1000 | 262144 | 262144 | |
19 | 1000 | 262144 | 262144 | |
20 | 1000 | 262144 | 262144 | |
21 | 1000 | 262144 | 262144 | |
22 | 1000 | 262144 | 262144 | |
23 | 1000 | 262144 | 262144 | |
24 | 1000 | 262144 | 262144 | |
25 | 1000 | 262144 | 262144 | |
26 | 1000 | 262144 | 262144 | |
27 | 1000 | 262144 | 262144 | |
28 | 1000 | 262144 | 262144 | |
29 | 1000 | 262144 | 262144 | |
30 | 1000 | 262144 | 262144 | |
31 | 1000 | 262144 | 262144 | |
32 | 1000 | 262144 | 262144 | |
33 | 1000 | 262144 | 262144 | |
34 | 1000 | 262144 | 262144 | |
35 | 1000 | 262144 | 262144 | |
36 | 1000 | 262144 | 262144 | |
37 | 1000 | 262144 | 262144 | |
38 | 1000 | 262144 | 262144 | |
39 | 1000 | 262144 | 262144 | |
40 | 1000 | 262144 | 262144 | |
41 | 1000 | 262144 | 262144 | |
42 | 1000 | 262144 | 262144 | |
43 | 1000 | 262144 | 262144 | |
44 | 1000 | 262144 | 262144 | |
45 | 1000 | 262144 | 262144 | |
46 | 1000 | 262144 | 262144 | |
47 | 1000 | 262144 | 262144 | |
48 | 1000 | 262144 | 262144 | |
49 | 1000 | 262144 | 262144 | |
50 | 1000 | 262144 | 262144 | |
51 | 1000 | 262144 | 262144 | |
52 | 1000 | 262144 | 262144 | |
53 | 1000 | 262144 | 262144 | |
54 | 1000 | 262144 | 262144 | |
55 | 1000 | 262144 | 262144 | |
56 | 1000 | 262144 | 262144 | |
57 | 1000 | 262144 | 262144 | |
58 | 1000 | 262144 | 262144 | |
59 | 1000 | 262144 | 262144 | |
60 | 1000 | 262144 | 262144 | |
61 | 1000 | 262144 | 262144 | |
62 | 1000 | 262144 | 262144 | |
63 | 1000 | 262144 | 262144 | |
64 | 1000 | 262144 | 262144 | |
65 | 1000 | 262144 | 262144 | |
66 | 1000 | 262144 | 262144 | |
67 | 1000 | 262144 | 262144 | |
68 | 1000 | 262144 | 262144 | |
69 | 1000 | 262144 | 262144 | |
70 | 1000 | 262144 | 262144 | |
71 | 1000 | 262144 | 262144 | |
72 | 1000 | 262144 | 262144 | |
73 | 1000 | 262144 | 262144 | |
74 | 1000 | 262144 | 262144 | |
75 | 1000 | 262144 | 262144 | |
76 | 1000 | 262144 | 262144 | |
77 | 1000 | 262144 | 262144 | |
78 | 1000 | 262144 | 262144 | |
79 | 1000 | 262144 | 262144 | |
80 | 1000 | 262144 | 262144 | |
81 | 1000 | 262144 | 262144 |