kananasgarli90

Bicoloring

Sep 25th, 2020
719
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> edges[1001];
  4. int u, v, used[1001], n, m, color = 1, flag;
  5.  
  6. void dfs(int x){
  7.     for(int i = 0; i < edges[x].size(); i++){
  8.         int vertex = edges[x][i];
  9.         if(used[vertex] == 0){
  10.             used[vertex] = -used[x];
  11.             dfs(vertex);
  12.         }
  13.     }
  14. }
  15. int main()
  16. {    
  17.     while(cin>>n && n != 0){
  18.         cin>>m;
  19.         while(m--){
  20.             cin>>u>>v;
  21.             edges[u].push_back(v);
  22.             edges[v].push_back(u);
  23.         }
  24.         used[1] = 1;
  25.         dfs(1);
  26.         for(int i = 1; i <= n && flag != 1; i++){
  27.             for(int j = 0; j < edges[i].size(); j++){
  28.                 int a = i;
  29.                 int b = edges[i][j];
  30.                 if(used[a] == used[b]){
  31.                     flag = 1;
  32.                     break;
  33.                 }
  34.             }
  35.         }
  36.         if(flag == 1){
  37.             cout<<"NOT BICOLOURABLE."<<endl;
  38.         }
  39.         else{
  40.             cout<<"BICOLOURABLE."<<endl;
  41.         }
  42.         flag = 0;
  43.         for(int i = 1; i <= n; i++){
  44.             edges[i].clear();
  45.             used[i] = 0;
  46.         }
  47.     }
  48.  
  49. }
RAW Paste Data