arujbansal

routes

Jan 22nd, 2021 (edited)
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.50 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. void dbg_out() { cerr << endl; }
  6. template<typename Head, typename... Tail>
  7. void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
  8. #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
  9.  
  10. #define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
  11. #define all(x) (x).begin(), (x).end()
  12. #define sz(x) (int) (x).size()
  13. // #define int long long
  14.  
  15. const int MXN = 5e5 + 5, INF = 1e9 + 5;
  16. pair<int, int> parent[MXN];
  17. int bipartite[MXN], compSz[MXN];
  18.  
  19. void make_set(int v) {
  20.     parent[v] = make_pair(v, 0);
  21.     compSz[v] = 0;
  22.     bipartite[v] = true;
  23. }
  24.  
  25. pair<int, int> find_set(int v) {
  26.     if (v != parent[v].first) {
  27.         int parity = parent[v].second;
  28.         parent[v] = find_set(parent[v].first);
  29.         parent[v].second ^= parity;
  30.     }
  31.     return parent[v];
  32. }
  33.  
  34. void add_edge(int a, int b) {
  35.     pair<int, int> pa = find_set(a);
  36.     a = pa.first;
  37.     int x = pa.second;
  38.  
  39.     pair<int, int> pb = find_set(b);
  40.     b = pb.first;
  41.     int y = pb.second;
  42.  
  43.     if (a == b) {
  44.         if (x == y)
  45.             bipartite[a] = false;
  46.     } else {
  47.         if (compSz[a] < compSz[b])
  48.             swap (a, b);
  49.         parent[b] = make_pair(a, x^y^1);
  50.         bipartite[a] &= bipartite[b];
  51.         if (compSz[a] == compSz[b])
  52.             ++compSz[a];
  53.     }
  54. }
  55.  
  56. bool is_bipartite(int v) {
  57.     return bipartite[find_set(v).first];
  58. }
  59.  
  60. void solve() {
  61.     int N, M, Q;
  62.     cin >> N >> M >> Q;
  63.  
  64.     for (int i = 0; i < N; i++)
  65.         make_set(i);
  66.  
  67.     for (int i = 0; i < M; i++) {
  68.         int u, v;
  69.         cin >> u >> v;
  70.  
  71.         add_edge(u, v);
  72.     }
  73.  
  74.     for (int i = 0; i < N; i++) {
  75.         find_set(i);
  76. //        dbg(i, parent[i].first, parent[i].second);
  77.     }
  78.  
  79.     while (Q--) {
  80.         int u, v;
  81.         cin >> u >> v;
  82.  
  83.         if (parent[u].first != parent[v].first) {
  84.             cout << "none\n";
  85.         } else if (!is_bipartite(u)) {
  86.             cout << "both\n";
  87.         } else {
  88. //            dbg(u, v, parent[u].second, parent[v].second, parent[u].first);
  89.             int val = parent[u].second ^ parent[v].second;
  90.             if (val & 1) cout << "odd\n";
  91.             else cout << "even\n";
  92.         }
  93.     }
  94. }
  95.  
  96. signed main() {
  97.     ios_base::sync_with_stdio(false);
  98.     cin.tie(nullptr);
  99.  
  100. #ifdef local
  101.     freopen("input.txt", "r", stdin);
  102.     freopen("output.txt", "w", stdout);
  103. #endif
  104.  
  105.     int TC = 1;
  106.     // cin >> TC;
  107.     while (TC--) solve();
  108. }
Add Comment
Please, Sign In to add comment