SHARE
TWEET

Untitled

a guest Dec 19th, 2018 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <string>
  5. using namespace std;
  6. vector < vector<int> > g1(1000);
  7. vector<int> used;
  8. int k =1;
  9. void dfs (int v) {
  10.     used[v] = k;
  11.    
  12.     for (int i = 0 ; i < int(g1[v].size()); ++i)
  13.         if (!used[g1[v][i]]){k =3-k;
  14.             dfs (g1[v][i]);
  15. }
  16.         else if(used[g1[v][i]] == used[v]){cout << "NO";exit(0);}
  17. }
  18. int main() {
  19.     ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
  20.     int n;cin >> n;
  21.     int m; cin >> m;
  22.     for(int i = 0 ; i < m; i++){
  23.         int x,y; cin >> x >> y;
  24.         g1[x-1].push_back(y-1);
  25.         g1[y-1].push_back(x-1);
  26.     }
  27.     for(int i = 0; i < n;i++) used.push_back(0);
  28.     for(int i = 0; i < n; i++){
  29.         if(used[i] == 0) dfs(i);
  30.     }cout<<"YES" << '\n';
  31. for(int i = 0; i < n;i++) cout << used[i] << ' ';
  32. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top