kananasgarli90

Bicoloring

Oct 29th, 2020
764
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector<int>g[1001];
  4. int n, m, u, v, color[1001];
  5. void dfs(int s){
  6.     for(int i = 0; i < g[s].size(); i++){
  7.         u = g[s][i];
  8.         if(color[u] == 0){
  9.             color[u] = -color[s];
  10.             dfs(u);
  11.         }
  12.     }
  13. }
  14. int main()
  15. {
  16.  
  17.     while(cin>>n){
  18.         if(n == 0){
  19.             break;
  20.         }
  21.         cin>>m;
  22.         while(m--){
  23.             cin>>u>>v;
  24.             g[u].push_back(v);
  25.             g[v].push_back(u);
  26.         }
  27.         color[1] = 1;
  28.         dfs(1);
  29.         int flag = 0;
  30.         for(int i = 1; i <= n && flag != 1; i++){
  31.             for(int j = 0; j < g[i].size(); j++){
  32.                 u = i;
  33.                 v = g[i][j];
  34.                 if(color[u] == color[v]){
  35.                     flag = 1;
  36.                     break;
  37.                 }
  38.             }
  39.         }
  40.         if(flag == 0){
  41.             cout<<"BICOLOURABLE."<<endl;
  42.         }
  43.         else{
  44.             cout<<"NOT BICOLOURABLE."<<endl;
  45.         }
  46.         for(int i = 1; i <= n; i++){
  47.             color[i] = 0;
  48.             g[i].clear();
  49.         }
  50.     }
  51. }
  52.  
RAW Paste Data