Sunjaree

UVA-10004 BICOLORING

Oct 25th, 2020
831
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using  namespace  std;
  3.  
  4. #define endl     "\n"
  5. #define ll       long long
  6. #define PI       acos(-1.0)
  7. #define test     cout<<"\n****\n"
  8. #define LCM(a,b) ((a/__gcd(a,b))*b)
  9. #define precise  fixed(cout);cout<<setprecision(20)
  10. #define fast     ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  11.  
  12.  
  13. vector<int>grap[210];
  14. char color[210];
  15. bool BFS(int node,int root){
  16.  
  17.     memset(color,'*',sizeof(color));
  18.     color[root] = 'R';
  19.  
  20.     queue<int> que;
  21.     que.push(root);
  22.  
  23.     while (!que.empty()){
  24.  
  25.         int parent = que.front();
  26.         que.pop();
  27.         char childColor;
  28.         if(color[parent]=='R'){
  29.             childColor = 'L';
  30.         } else{
  31.             childColor = 'R';
  32.         }
  33.  
  34.         for (int i = 0; i < grap[parent].size(); i++) {
  35.             int child = grap[parent][i];
  36.             if(color[child]=='*'){
  37.                 color[child] = childColor;
  38.             } else if(color[child]==color[parent]){
  39.                 return false;
  40.             }else{
  41.                 continue;
  42.             }
  43.             que.push(child);
  44.         }
  45.     }
  46.  
  47.     return true;
  48. }
  49.  
  50. int main() {
  51.     fast;
  52.     int node,edge;
  53.     while (cin>>node && node){
  54.  
  55.         cin>>edge;
  56.         int nod,ed;
  57.         for(int i=0;i<edge;i++){
  58.             cin>>nod>>ed;
  59.             grap[nod].push_back(ed);
  60.             grap[ed].push_back(nod);
  61.         }
  62.  
  63.         if(BFS(node,nod)){
  64.             cout<<"BICOLORABLE.\n";
  65.         } else{
  66.             cout<<"NOT BICOLORABLE.\n";
  67.         }
  68.  
  69.         for (auto& v : grap) {
  70.             v.clear();
  71.         }
  72.     }
  73.  
  74.     return 0;
  75. }
RAW Paste Data