d100: Q-7-8. 小寶的著色問題
Tags : 圖論
Accepted rate : 73人/84人 ( 87% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-03-03 10:01

Content

小寶有個布娃娃,娃娃會變化。娃娃身上有一些圖案,這些圖案是由一些圓圈和一些線條組成,每個線條連接著某兩個不同的圓圈。

小寶很喜歡著色,他決定要把這些圓圈塗上紅色或藍色,他覺得有線條相連的圓圈最好塗上不一樣的顏色,但是因為圓圈很多,他不知道能不能夠完成這樣的想法,請你幫他計算看看是否可以有辦法完成這樣的著色。

Input

第一行有一個整數T,代表接下來有T張圖的資料要計算。

每張圖資料的第一行是兩個整數 n 與 m,代表有 n 個圓圈與 m 個線條,

第二行有 2m 個整數,每兩個一組代表一根線條所連接的兩個圓圈編號,圓圈是以0~n-1 編號。

n 不超過 1e4,m 不超過 1e5。

T 不超過 20。

Output

依序每一行輸出一張圖是否可以正確著色,如果是,則輸出 yes,否則輸出 no。

Sample Input #1
2
2 0
4 3
0 3 3 2 2 0
Sample Output #1
yes
no
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <50M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <50M
公開 測資點#3 (20%): 1.0s , <50M
公開 測資點#4 (20%): 1.0s , <50M
Hint :

題目給的不一定是  conected graph

Tags:
圖論
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]


ID User Problem Subject Hit Post Date
130
winniethepoo... (winnie the pooh)
d100
DFS要記得cin加速
125 2022-09-17 12:24