题意：输入一个简单（无多重边和自环）的连通无向图，判断该图是否能用黑白两种颜色对顶点染色，使得每条边的两个端点为不同颜色.
解法：由于无自连通节点存在，所以只需进行一次宽搜，遍历所有的点和所有的边,判断能否用两种颜色进行染色即可！宽搜时对访问点需要进行颜色判断和标记！
1 #include<iostream> 2 #include<queue> 3 #include<memory.h> 4 using namespace std; 5 6 int colors[1001]; 7 bool paths[1001][1001]; 8 int main(){ 9 int vertices,edges; 10 int from,dest; 11 memset(paths,false,sizeof(paths)); 12 memset(colors,0,sizeof(colors)); 13 14 cin >> vertices >> edges; 15 while(edges--){ 16 cin >> from >>dest; 17 paths[from][dest] = true; 18 paths[dest][from] = true; 19 } 20 21 //breadth-first search 22 queue<int> que; 23 int current ; 24 que.push(1); 25 colors[1] = 1; 26 while(!que.empty()){ 27 current = que.front(); 28 for(int j=1;j<=vertices;j++){ 29 if(paths[current][j] == true){ 30 if(colors[current] == colors[j]) 31 { 32 cout << "no"<<endl; 33 return 0; 34 } 35 if(colors[j] == 0){ 36 que.push(j); 37 if(colors[current] == 1){ 38 colors[j] = 2; 39 } 40 else{ 41 colors[j] = 1; 42 } 43 } 44 } 45 } 46 //pop the front node 47 que.pop(); 48 } 49 //output 50 cout<<"yes"<<endl; 51 return 0; 52 }