回分類題庫
h186: D.最大不團問題
關鍵字: NPSC 2017 高中組決賽

測資點 : 9 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 41 Times / 37 Users | Submit : 153 Times / 46 Users | Accepted rate : 80%
題目加入時間 : 2018-10-08 10:51

Content: 简体中文

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

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

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

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

Input:

測試資料第一行包含一個正整數 T,代表有幾組測試資料。 

每組測試資料第一行有兩個數字 N, M,分別表示圖的頂點個數以及邊數。

接下來 M 行,每行包含兩個數字 ui, vi,表示 ui 與 vi 之間有一條邊。 

Output:

每組測試資料輸出一個數字於一行,表示最大不團的頂點個數。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
3 3
1 2
2 3
1 3
4 4
1 2
2 3
3 4
1 4

Sample Output :

0
4

Hint :

Author :

NPSC 2017 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum