fork(2) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <numeric>
  4. using namespace std;
  5.  
  6. vector<int> parent, sz;
  7.  
  8. int find(int i) {
  9.     if(parent[i]==i) return i;
  10.     return parent[i]=find(parent[i]);
  11. }
  12.  
  13. void merge(int i, int j) {
  14.     int p1=find(i);
  15.     int p2=find(j);
  16.  
  17.     if(p1==p2) return;
  18.     if(sz[p1]<sz[p2]) {
  19.         parent[p1]=p2;
  20.         sz[p2]+=sz[p1];
  21.     } else {
  22.         parent[p2]=p1;
  23.         sz[p1]+=sz[p2];
  24.     }
  25. }
  26.  
  27. int main() {
  28. 	vector<vector<int>> allowedSwaps={{0,4},{4,2},{1,3},{1,4}};
  29.  
  30.     int n=5;	//hard-code for now
  31.     sz.resize(n,1);
  32.     parent.resize(n);
  33.     iota(begin(parent),end(parent),0);
  34.  
  35. 	cout<<"Parents before: \n";
  36.     for(auto e: parent)
  37.         cout<<e<<" ";
  38.     cout<<"\n";
  39.  
  40.     for(vector<int>& currswap: allowedSwaps) {
  41.         merge(currswap[0],currswap[1]);
  42.     }
  43.  
  44.     cout<<"Parents after: \n";
  45.     for(auto e: parent)
  46.         cout<<e<<" ";
  47.     cout<<"\n";
  48.  
  49. 	return 0;
  50. }
Success #stdin #stdout 0.01s 5544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Parents before: 
0 1 2 3 4 
Parents after: 
0 0 0 1 0
https://ideone.com/vaU5Ni
language:
C++ (gcc 8.3)
created:
3 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!