fork download
copy 
  1. #include <bits/stdc++.h>
  2. const int N = 1e5;
  3. #define ll long long
  4. using namespace std;
  5.  
  6. int n, m;
  7. int a[N+3];
  8. vector<map<int, int>> v(N+3);
  9. int parent[N+3], sz[N+3];
  10.  
  11. void make(){
  12.     for(int i=1;i<=n;i++){
  13.         v[i][a[i]] = 1;
  14.         parent[i] = i;
  15.         sz[i] = 1;
  16.     }
  17.  
  18. }
  19.  
  20. int find(int v){
  21.     if(v == parent[v])return v;
  22.     int res = find(parent[v]);
  23.     parent[v] = res;
  24.     return res;
  25. }
  26.  
  27. void Union(int a, int b){
  28.     a = find(a);
  29.     b = find(b);
  30.     if(a != b){
  31.         if(sz[a] < sz[b])swap(a, b);
  32.         parent[b] = a;
  33.         sz[a] += sz[b];
  34.         for(auto res : v[b])v[a][res.first] += res.second;
  35.         v[b].clear();
  36.     }
  37. }
  38.  
  39. void query(int a, int b){
  40.     a = find(a);
  41.     if(v[a].find(b) != v[a].end())cout<<v[a][b]<<"\n";
  42.     else cout<<0<<"\n";
  43. }
  44.  
  45. int main(){
  46.     ios_base::sync_with_stdio(0);
  47.     cin.tie(0);
  48.     cin>>n>>m;
  49.     for(int i=1;i<=n;i++){
  50.         cin>>a[i];
  51.     }
  52.  
  53.     make();
  54.     while(m--){
  55.         int x, y, z;
  56.         cin>>x>>y>>z;
  57.         if(x == 1)Union(y, z);
  58.         else query(y, z);
  59.     }
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0.01s 7684KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rsOB8w
language:
C++14 (gcc 8.3)
created:
5 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!