1209 . 圖論 之 二分圖測試
TopCoder
Description
給你一個圖(Graph)，請問這個圖是否為一個二分圖(bipartite graph)？
所謂的二分圖，就是存在一種分法，把所有頂點分成兩個點集X和Y，其中X以及Y內部的頂點互不相鄰。
Input Format
輸入可能包含多筆測試資料。
每筆測試資料的第一列有兩個整數n,m(1<=n<=40,000；0<=m<=500,000)，分別代表一個圖的點數和邊數。
點的編號是從1到n。
接下來有m列，每列有兩個以空白隔開的正整數，代表一條邊所連的兩個端點編號。
當n=m=0時代表輸入結束。
Output Format
對於每筆測試資料，若該圖是二分圖，請輸出Yes，否則輸出No。
Sample Input 1
3 2
1 2
2 3
3 3
1 2
2 3
3 1
0 0
1 2
2 3
3 3
1 2
2 3
3 1
0 0
Sample Output 1
Yes
No
No
Hints
※2008/08/25：題目敘述修正，感謝math120908。 by Tmt
Problem Source
原TIOJ1209 / TIOJ 2008例行賽03 (prob A)。經典問題練習。Problem Setter：Tmt。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 50 |
| 2 | 1 | 50 |