[TIOJ] 1209. 圖論 之 二分圖測試

題目連結:http://tioj.infor.org/problems/1209

---

直接BFS跑一遍，看他有沒有被設過了，如果有就看他是不是跟他爸一樣，如果沒有就把他設成跟他爸一樣

#include <stdio.h>
#include <vector>
#include <queue>
#include <bitset>

#define PB push_back
using std::vector;

using std::bitset;
using std::queue;

bitset<40000 + 10> checked;
bitset<40000 + 10> which;

int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	while(n!=0||m!=0){
		checked=0;
		which=0;
		vector<int> graph[40000 + 10];
		for(int i=0;i<m;i++){
			int a,b;
			scanf("%d %d",&a,&b);
			graph[a].PB(b);
			graph[b].PB(a);
		}
		queue<int> q;
		bool ok=true;
		for(int i=1;i<=n;i++){
			if(checked[i]) continue;
			checked[i]=1;
			which[i]=1;
			q.push(i);
			while(!q.empty()){
				int cur = q.front();
				q.pop();
				for(int j=0;j<graph[cur].size();j++){
					if(checked[graph[cur][j]]){
						if(which[graph[cur][j]] == which[cur]){
							ok=0;
							break;
						}
					}else{
						checked[graph[cur][j]]=1;
						which[graph[cur][j]] = !which[cur];
						q.push(graph[cur][j]);
					}
				}
				if(!ok)break;
			}
			if(!ok)break;
		}
		puts(ok?"Yes":"No");
		scanf("%d %d",&n,&m);
	}
	return 0;
}