c889: 2. 二分圖
Tags :
Accepted rate : 28人/32人 ( 88% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-01-29 19:59

Content

如果一個無向圖 (undirected graph) G 的頂點集合 (vertex set) 可被分割為兩個互不相交的非空子集 A 和 B,使得 G中每一條邊 (edge) 的兩個頂點分別屬於這兩個子集,那麼我們稱G 為一個「二分圖」 (bipartite graph),並稱 A 和 B 是一個有效分割。例如: 圖一(a)是一個二分圖,因為我們可以取 A = {2, 3, 5, 9} 和 B = {1, 4, 6, 7, 8, 10, 11} 使得每一條邊的兩個頂點分別屬於 A 和 B;圖一(b)也是一個二分圖,因為 A = {1, 4, 6, 8, 11, 13} 和 B = {2, 3, 5, 7, 9, 10, 12} 是一個有效分割;圖一(c)則不是一個二分圖,因為不存在任何有效分割。

一個圖 G 是不是二分圖可以判斷如下。我們試著將 G 中的每一個頂點著上白色或黑色。為了方便說明,我們假設 G 是一個連通圖 (connected graph),也就是說 G 中任兩個頂點間都存在一條路徑:而且我們稱白和黑是兩個對立的顏色。開始時我們任選一頂點著上白色,其餘所有頂點都沒有顏色。然後重複以下規則直到每一個頂點都被著上顏色:

 (R) 挑一個有顏色的頂點,將所有和它相鄰的頂點著上對立的顏色。

在過程中如果發現一個已經有顏色的頂點因為 (R) 這個規則必須被著上不同的顏色,那麼就出現了矛盾,G 不是二分圖,可以停止著色。否則,可以看出在著色結束後,白和黑兩群頂點所代表兩個子集 A 和 B 是一個有效分割。

Input

測試資料第一行有兩個數字 n, m ,第一個數字 n 表示圖中的頂點數, 1 < n ≤ 105 ,第二個數字 m 表示圖中的邊數, 1 ≤ m ≤ 106,接下來會有 m 行,每行有兩個正整數 i, j,i ≠ j,1 ≤ i ≤ n,1 ≤ j ≤ n,表示頂點 i 和 j 之間有一條邊。(不會有重複邊)

Output

請輸出一行,如果給定的無向圖 G 不是一個二分圖,請輸出 0;如果給定的無向圖 G 是一個二分圖,請輸出最小的整數 k 滿足 G 存在一個有效分割 A 和 B,其中 A 中的頂點數是 k。

Sample Input
第二子題 輸入範例:
4 4
1 2
4 3
2 4
1 3

第三子題 輸入範例:
11 13
1 2
11 9
5 7
3 11
5 6
3 1
6 9
2 4
4 5
8 5
9 8
9 10
8 2

第四子題 輸入範例:
8 10
6 5
1 4
5 7
8 6
3 1
2 1
5 4
2 5
8 7
6 3

第五子題 輸入範例:
13 12
8 7
1 2
3 6
5 4
1 3
9 8
11 12
10 8
6 5
3 4
6 2
13 12
Sample Output
第二子題 輸出範例:
2

第三子題 輸出範例:
4

第四子題 輸出範例:
0

第五子題 輸出範例:
5
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (13%): 1.0s , <1K
公開 測資點#1 (1%): 1.0s , <1K
公開 測資點#2 (1%): 1.0s , <1K
公開 測資點#3 (11%): 1.0s , <1K
公開 測資點#4 (1%): 1.0s , <1K
公開 測資點#5 (1%): 1.0s , <1K
公開 測資點#6 (1%): 1.0s , <1K
公開 測資點#7 (1%): 1.0s , <1K
公開 測資點#8 (31%): 1.0s , <1K
公開 測資點#9 (1%): 1.0s , <1K
公開 測資點#10 (1%): 1.0s , <1M
公開 測資點#11 (1%): 1.0s , <1M
公開 測資點#12 (1%): 1.0s , <1M
公開 測資點#13 (1%): 1.0s , <1M
公開 測資點#14 (1%): 1.0s , <1M
公開 測資點#15 (1%): 1.0s , <1M
公開 測資點#16 (1%): 1.0s , <1M
公開 測資點#17 (1%): 1.0s , <1M
公開 測資點#18 (6%): 1.0s , <1K
公開 測資點#19 (1%): 1.0s , <1K
公開 測資點#20 (1%): 1.0s , <1K
公開 測資點#21 (1%): 1.0s , <1M
公開 測資點#22 (1%): 1.0s , <1M
公開 測資點#23 (1%): 1.0s , <1M
公開 測資點#24 (1%): 1.0s , <1M
公開 測資點#25 (1%): 1.0s , <1M
公開 測資點#26 (1%): 1.0s , <1M
公開 測資點#27 (1%): 1.0s , <1M
公開 測資點#28 (8%): 1.0s , <1K
公開 測資點#29 (1%): 1.0s , <10M
公開 測資點#30 (1%): 1.0s , <10M
公開 測資點#31 (1%): 1.0s , <10M
公開 測資點#32 (1%): 1.0s , <10M
公開 測資點#33 (1%): 1.0s , <10M
公開 測資點#34 (1%): 1.0s , <50M
公開 測資點#35 (1%): 1.0s , <50M
Hint :

本題共有四個子題,每一子題可有多筆測試資料:

第一子題,n ≤ 3 且 G 是連通圖,解出可以獲得 15 分;

第二子題,n ≤ 4 且 G 是連通圖,解出可以獲得 15 分;

第三子題,n ≤ 104 且 G 是連通圖,解出可以獲得 40 分;

第四子題,n ≤ 104 (G 不一定是連通圖),解出可以獲得 15 分;

第五子題,n ≤ 105 且 m ≤ 106 (G 不一定是連通圖),解出可以獲得 15 分。

Tags:
出處:
107學年度全國資訊學科能力競賽 [管理者:
icube (輸光光)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」