fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. const int MAXN = 1000005;
  7.  
  8. int parent_node[MAXN];
  9. int size_node[MAXN];
  10.  
  11. int find_set(int v) {
  12.     if (v == parent_node[v])
  13.         return v;
  14.     return parent_node[v] = find_set(parent_node[v]);
  15. }
  16.  
  17. void union_sets(int a, int b, int &components) {
  18.     a = find_set(a);
  19.     b = find_set(b);
  20.  
  21.     if (a != b) {
  22.         if (size_node[a] < size_node[b]) {
  23.             swap(a, b);
  24.         }
  25.         parent_node[b] = a;
  26.         size_node[a] += size_node[b];
  27.         components--;
  28.     }
  29. }
  30.  
  31. int main() {
  32. 	ios_base::sync_with_stdio(false);
  33.     cin.tie(NULL);
  34.  
  35.     int n;
  36.     if (!(cin >> n)) return 0;
  37.     for (int i = 1; i <= n; i++) {
  38.         parent_node[i] = i;
  39.         size_node[i] = 1;
  40.     }
  41.  
  42.     int components = n; 
  43.  
  44.     for (int i = 1; i <= n; i++) {
  45.         int key_location;
  46.         cin >> key_location;
  47.         union_sets(i, key_location, components);
  48.     }
  49.     cout << components << "\n";
  50.  
  51.     return 0;
  52. }
Success #stdin #stdout 0s 5572KB
comments (?)
stdin
copy 
4
2
1
2
4
stdout
copy 
2
https://ideone.com/MMzX0Y
language:
C++14 (gcc 8.3)
created:
18 hours 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!