AlbertMourato

Untitled

Mar 1st, 2016
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.43 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <bits/stdc++.h>
  3. //%lld
  4. typedef long long ll;
  5. #define si(a) scanf("%d", &a)
  6. #define sii(a, b) scanf("%d%d", &a, &b)
  7. using namespace std;
  8.  
  9. int main(){
  10.     //freopen("in.txt", "r", stdin);
  11.     //freopen("out.txt", "w", stdout);
  12.     vector<int>grafo[1000];
  13.     queue<int> fila;
  14.     int cor[1000];
  15.     int v, a, b, aux;
  16.     bool c = true;
  17.     while(cin>>v){
  18.         if(v==0)break;
  19.         else{
  20.             c = true;
  21.             for(int i = 0;i<v;i++){
  22.                 sii(a, b);
  23.                 grafo[a].push_back(b);
  24.                 grafo[b].push_back(a);
  25.             }
  26.             fila.push(0);
  27.             cor[0] = 1;
  28.             while(!fila.empty()&&c){
  29.                 aux = fila.front();
  30.                 fila.pop();
  31.                 for(int i = 0;i<grafo[aux].size();i++){
  32.                     if(cor[grafo[aux][i]]==0){//nao ta pintado
  33.                         if(cor[aux]==1)cor[grafo[aux][i]] = 2;
  34.                         else cor[grafo[aux][i]] = 1;
  35.                         fila.push(grafo[aux][i]);
  36.                     }else{//ta pintado ja
  37.                         if((cor[aux]==cor[grafo[aux][i]])||(cor[aux]==cor[grafo[aux][i]])){
  38.                             c = false;
  39.                             break;
  40.                         }
  41.                     }
  42.                 }
  43.             }
  44.             if(c)puts("BICOLORABLE.");
  45.             else puts("NOT BICOLORABLE.");
  46.         }
  47.     }
  48. }
Advertisement
Add Comment
Please, Sign In to add comment