10004 Bicoloring

題目原文

題目說明
只有兩種顏色，且相鄰兩點需不同色，若可以達成，則輸出 BICOLORABLE，反之輸出 NOT BICOLORABLE。

思路
首先以 vector 建立表格來儲存與某節點相鄰的其他節點，以 queue 來儲存節點走訪的順序。
建立好連通表後，開始走訪，走訪做兩種事情：著色和檢查是否同色，可隨機從某點開始(以下程式碼以 n1 當第一個節點)，將其 push 進 queue 裡並著上顏色，塗完顏色後以 current 記住後 pop 出去，
接著開始替相鄰節點(由連通表依序取出)著色，若相鄰節點尚未著色，則 push 到 queue 裡，當作下一個要走訪的 current，並著上與當前 current 相反顏色；已著色則檢查是否與當前 current 同色，同色則可確定非 bicolorable。著完後色都沒問題即為 bicolorable。

簡言之，
1. 建連通表  2. 按連通表依序著色  3. 著色過程中檢查是否符合規定。

#include<cstdio>
#include<vector>
#include<queue>
 
int main()
{
 int node;
 while(scanf("%d", &node) && node)
 {
  int edge, n1, n2; 
  int color[200] = {0};
  bool check = true;
  std::vector<int> vec[205];          // 所在列數代表它是第幾個點 後面push進和它連接的點
  std::queue<int> que;
 
  scanf("%d", &edge);
  for(int i = 0; i < edge; i++)
  {
   scanf("%d %d", &n1, &n2);
   vec[n1].push_back(n2);       // 建連通表 記得兩邊互相連接 
   vec[n2].push_back(n1);
  }
  
  que.push(n1);
  color[n1] = 1;
 
  while(!que.empty() && check)      // 開始走訪 
  {
   int current = que.front();      // 先用current存起來
   que.pop();
   
   for(int i = 0; i < vec[current].size(); i++)
   {
    int j = vec[current][i];
    if(color[j] == 0)       // 還沒上過色
    {
     que.push(j);
     color[j] = -color[current];
    } 
    else if(color[j] == color[current])
    {
     check = false;
     break;
    } 
   }
  } 
  if(check)
   printf("BICOLORABLE.\n");
  else 
   printf("NOT BICOLORABLE.\n");  
 }
}