fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4.  
  5. const int MAXN = 1e5 + 15;
  6. const int oo   = 1e9 + 7;
  7.  
  8. int N, Q;
  9. int A[MAXN];
  10.  
  11. struct Dosu {
  12.     int par[MAXN], sz[MAXN];
  13.     map<int, int> m[MAXN];
  14.     vector<int> g[MAXN];
  15.  
  16.     void INIT() {
  17.         for (int i = 1; i <= N; i++) {
  18.             sz[i] = 1;
  19.             par[i] = i;
  20.             g[i].push_back(A[i]);
  21.             m[i][A[i]] = 1;
  22.         }
  23.     }
  24.  
  25.     int find_set(int u) {
  26.         return (par[u] == u ? u : par[u] = find_set(par[u]));
  27.     }
  28.  
  29.     void union_set(int u, int v) {
  30.         u = find_set(u), v = find_set(v);
  31.         if (u == v) return;
  32.         if (sz[u] < sz[v]) swap(u, v);
  33.         par[v] = par[u];
  34.         sz[u] += sz[v];
  35.         for (auto E : g[v]) {
  36.             m[u][E]++;
  37.             g[u].push_back(E);
  38.         }
  39.     }
  40. } DSU;
  41.  
  42. signed main() {
  43.     ios_base::sync_with_stdio(0);
  44.     cin.tie(0); cout.tie(0);
  45.  
  46.  
  47.     cin >> N >> Q;
  48.  
  49.     for (int i = 1; i <= N; i++) cin >> A[i];
  50.  
  51.     DSU.INIT();
  52.  
  53.  
  54.     for (int i = 1; i <= Q; i++) {
  55.         int t, a, b;
  56.         cin >> t >> a >> b;
  57.         if (t == 1) DSU.union_set(a, b);
  58.         else {
  59.             cout << DSU.m[DSU.find_set(a)][b] << '\n';
  60.         }
  61.     }
  62. }
  63.  
Success #stdin #stdout 0.01s 10704KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0eaLtm
language:
C++ (gcc 8.3)
created:
30 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!