fork download
copy 
  1. /*
  2.   Copyright 2013,2016 Marek "p2004a" Rusinowski
  3.   Disjoint-set data structure(Find&Union)
  4. */
  5. #include <cstdio>
  6. #include <vector>
  7. #include <numeric>
  8.  
  9. using namespace std;
  10.  
  11. class FindUnion {
  12.   vector<int> root, rank;
  13.  
  14.  public:
  15.   FindUnion(int n) : root(n), rank(n) {
  16.   	iota(root.begin(), root.end(), 0);
  17.   }
  18.  
  19.   int find_set(int v) {
  20.     if (root[v] == v) return v;
  21.     root[v] = find_set(root[v]);
  22.     return root[v];
  23.   }
  24.  
  25.   void union_sets(int v, int u) {
  26.     v = find_set(v);
  27.     u = find_set(u);
  28.     if (rank[v] < rank[u]) {
  29.       root[v] = u;
  30.     } else if (rank[v] > rank[u]) {
  31.       root[u] = v;
  32.     } else {
  33.       root[v] = u;
  34.       ++rank[v];
  35.     }
  36.   }
  37. };
  38.  
  39. int main() {
  40.   int n, m;
  41.   scanf("%d %d\n", &n, &m);
  42.   FindUnion f(n);
  43.   int a, b;
  44.   char c;
  45.   for (int i = 0; i < m; ++i) {
  46.     scanf("%c", &c);
  47.     switch(c) {
  48.       case 'f': {
  49.         scanf("%d\n", &a);
  50.         printf("%d\n", f.find_set(a - 1) + 1);
  51.         break;
  52.       }
  53.       case 'u': {
  54.         scanf("%d %d\n", &a, &b);
  55.         f.union_sets(a - 1, b - 1);
  56.         break;
  57.       }
  58.     }
  59.   }
  60.   return 0;
  61. }
  62.  
Success #stdin #stdout 0s 3416KB
comments (?)
stdin
copy 
5 10
f 4
f 5
u 4 5
f 4
f 5
u 1 2
f 1
u 1 4
f 5
f 1
stdout
copy 
4
5
5
5
2
5
5
https://ideone.com/wB1jTr
Find&Union
language:
C++14 (gcc 8.3)
created:
8 years 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!