2045 . D.最大不團問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

96.1% (74/77)

Submission's AC Ratio

59.6% (186/312)

Tags

NPSC 2017-NPSC-fin

Description

在圖論領域中，對於一個無向圖而言，滿足兩兩之間有邊連接的頂點集合，被稱為該無向圖的團。團是圖論中的基本概念之一，用在很多數學問題以及圖的構造上。計算機科學中也有
對它的研究，儘管在一個圖中尋找給定大小的團達到了NP 完全的難度，人們還是研究過很多尋找團的算法。

即使尋找團的問題是如此的困難，但傳說中，某個小島舉行的ACM-ICPC 區域賽卻常常有最大團問題。即給定一張無向圖，找出一個頂點數最多的團。

身為一個專業的競賽選手，艾迪準備了最大團的codebook，以應付某小島賽區的題目。但今年該賽區居然不出最大團問題了，反而出了一道最大不團問題！即找一個最大的頂點集合，使得他並不是一個團。

由於艾迪已經驚慌失措了，你能夠幫助他解決這個問題嗎？

Input Format

測試資料第一行有兩個數字$N, M$，分別表示圖的頂點個數以及邊數。
接下來$M$ 行，每行包含兩個數字$u_i, v_i$，表示$u_i$ 與$v_i$ 之間有一條邊。

  • $1\leq N \leq 10^ 5$
  • $0\leq M \leq 10^ 5$
  • $1\leq u_i < v_i \leq N$
  • 不會有重邊，即任兩個頂點之間至多只有一條邊連接

Output Format

輸出一個數字於一行，表示最大不團的頂點個數。

Sample Input 1

3 3
1 2
2 3
1 3

Sample Output 1

0

Sample Input 2

4 4
1 2
2 3
3 4
1 4

Sample Output 2

4

Hints

Problem Source

2017 NPSC高中組決賽

Subtasks

No. Testdata Range Score
1 0~81 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1
1 1000 262144 262144 1
2 1000 262144 262144 1
3 1000 262144 262144 1
4 1000 262144 262144 1
5 1000 262144 262144 1
6 1000 262144 262144 1
7 1000 262144 262144 1
8 1000 262144 262144 1
9 1000 262144 262144 1
10 1000 262144 262144 1
11 1000 262144 262144 1
12 1000 262144 262144 1
13 1000 262144 262144 1
14 1000 262144 262144 1
15 1000 262144 262144 1
16 1000 262144 262144 1
17 1000 262144 262144 1
18 1000 262144 262144 1
19 1000 262144 262144 1
20 1000 262144 262144 1
21 1000 262144 262144 1
22 1000 262144 262144 1
23 1000 262144 262144 1
24 1000 262144 262144 1
25 1000 262144 262144 1
26 1000 262144 262144 1
27 1000 262144 262144 1
28 1000 262144 262144 1
29 1000 262144 262144 1
30 1000 262144 262144 1
31 1000 262144 262144 1
32 1000 262144 262144 1
33 1000 262144 262144 1
34 1000 262144 262144 1
35 1000 262144 262144 1
36 1000 262144 262144 1
37 1000 262144 262144 1
38 1000 262144 262144 1
39 1000 262144 262144 1
40 1000 262144 262144 1
41 1000 262144 262144 1
42 1000 262144 262144 1
43 1000 262144 262144 1
44 1000 262144 262144 1
45 1000 262144 262144 1
46 1000 262144 262144 1
47 1000 262144 262144 1
48 1000 262144 262144 1
49 1000 262144 262144 1
50 1000 262144 262144 1
51 1000 262144 262144 1
52 1000 262144 262144 1
53 1000 262144 262144 1
54 1000 262144 262144 1
55 1000 262144 262144 1
56 1000 262144 262144 1
57 1000 262144 262144 1
58 1000 262144 262144 1
59 1000 262144 262144 1
60 1000 262144 262144 1
61 1000 262144 262144 1
62 1000 262144 262144 1
63 1000 262144 262144 1
64 1000 262144 262144 1
65 1000 262144 262144 1
66 1000 262144 262144 1
67 1000 262144 262144 1
68 1000 262144 262144 1
69 1000 262144 262144 1
70 1000 262144 262144 1
71 1000 262144 262144 1
72 1000 262144 262144 1
73 1000 262144 262144 1
74 1000 262144 262144 1
75 1000 262144 262144 1
76 1000 262144 262144 1
77 1000 262144 262144 1
78 1000 262144 262144 1
79 1000 262144 262144 1
80 1000 262144 262144 1
81 1000 262144 262144 1
Submit
Status
Ranklist
Back to Top