Advertisement
arujbansal

Untitled

Feb 6th, 2021
167
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.79 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <map>
  5. #include <set>
  6. #include <array>
  7. #include <stack>
  8. #include <queue>
  9. #include <random>
  10. #include <numeric>
  11. #include <chrono>
  12. #include <utility>
  13. #include <iomanip>
  14.  
  15. using namespace std;
  16.  
  17. void dbg_out() { cerr << endl; }
  18. template<typename Head, typename... Tail>
  19. void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
  20. #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
  21.  
  22. #define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
  23. #define rng_seed(x) mt19937 rng(x)
  24. #define all(x) (x).begin(), (x).end()
  25. #define sz(x) (int) (x).size()
  26. // #define int long long
  27.  
  28. const int MXN = 1e5 + 1, INF = 1e9 + 1;
  29.  
  30. struct DSU {
  31.     int n;
  32.     vector<int> info;
  33.  
  34.     DSU(int n) : n(n) { info.assign(n, -1); }
  35.  
  36.     int get(int x) {
  37.         if (info[x] < 0) return x;
  38.         return info[x] = get(info[x]);
  39.     }
  40.  
  41.     void unite(int x, int y) {
  42.         x = get(x), y = get(y);
  43.         if (x == y) return;
  44.  
  45.         if (info[y] < info[x]) swap(x, y);
  46.         info[x] += info[y];
  47.         info[y] = x;
  48.     }
  49. };
  50.  
  51. void solve() {
  52.     int N, K, L;
  53.     cin >> N >> K >> L;
  54.  
  55.     DSU roads(N), railways(N);
  56.  
  57.     while (K--) {
  58.         int u, v;
  59.         cin >> u >> v;
  60.  
  61.         roads.unite(u - 1, v - 1);
  62.     }
  63.  
  64.     while (L--) {
  65.         int u, v;
  66.         cin >> u >> v;
  67.  
  68.         railways.unite(u - 1, v - 1);
  69.     }
  70.  
  71.     map<pair<int, int>, int> cnt;
  72.  
  73.     for (int i = 0; i < N; i++) {
  74.         int roadPar = roads.get(i), railwayPar = railways.get(i);
  75.  
  76.         cnt[{roadPar, railwayPar}]++;
  77.     }
  78.  
  79.     for (int i = 0; i < N; i++) {
  80.         int roadPar = roads.get(i), railwayPar = railways.get(i);
  81.  
  82.         cout << cnt[{roadPar, railwayPar}] << " ";
  83.     }
  84. }
  85.  
  86. signed main() {
  87.     ios_base::sync_with_stdio(false);
  88.     cin.tie(nullptr);
  89.  
  90.     int TC = 1;
  91.     // cin >> TC;
  92.     while (TC--) solve();
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement