kananasgarli90

Building teams

Oct 29th, 2020
596
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[100001];
  4. int n, m, u, v, color[100001], say;
  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.         else if(color[u] == color[s]){
  13.             say = 1;
  14.         }
  15.     }
  16. }
  17. int main()
  18. {
  19.     cin>>n>>m;
  20.     while(m--){
  21.         cin>>u>>v;
  22.         g[u].push_back(v);
  23.         g[v].push_back(u);
  24.     }
  25.     for(int i = 1; i <= n; i++){
  26.         if(color[i] == 0){
  27.             color[i] = 1;
  28.             dfs(i);
  29.         }
  30.     }
  31.     if(say == 1){
  32.         cout<<"IMPOSSIBLE"<<endl;
  33.     }
  34.     else{
  35.         for(int i = 1; i <= n; i++){
  36.             if(color[i] == 1){
  37.                 cout<<"1 ";
  38.             }
  39.             else{
  40.                 cout<<"2 ";
  41.             }
  42.         }
  43.     }
  44. }
  45.  
RAW Paste Data