fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int Arr[100], size[100];
  5.  
  6. int root (int i)
  7. {
  8.     while(Arr[ i ] != i)
  9.     {
  10.         Arr[ i ] = Arr[ Arr[ i ] ] ; 
  11. 		i = Arr[ i ]; 
  12. 	}
  13. 	return i;
  14. }
  15.  
  16. void weighted_union(int A,int B)
  17. {
  18.     int root_A = root(A);
  19.     int root_B = root(B);
  20.     if(size[root_A] < size[root_B ])
  21.     {
  22. 		Arr[ root_A ] = Arr[root_B];
  23. 		size[root_B] += size[root_A];
  24. 	}
  25.     else
  26.     {
  27. 		Arr[ root_B ] = Arr[root_A];
  28. 		size[root_A] += size[root_B];
  29. 	}
  30. }
  31.  
  32. void initialize( int N)
  33. {
  34.     for(int i = 0;i<N;i++)
  35.     {
  36. 		Arr[ i ] = i ;
  37. 		size[ i ] = 1;
  38. 	}
  39. }
  40.  
  41. int main() {
  42. 	// your code goes here
  43. 	initialize(6);
  44. 	weighted_union(1,2);
  45. 	weighted_union(2,4);
  46. 	weighted_union(3,5);
  47.  
  48.  
  49. 	map<int, vector<int> >m;
  50. 	for (int i=1;i<=5;i++) {
  51. 		if(m.find(Arr[i])!=m.end()){
  52. 			vector<int> x = m[Arr[i]];
  53. 			x.push_back(i);
  54. 			m[Arr[i]] = x;
  55. 		} else {
  56. 			vector<int> x;
  57. 			x.push_back(i);
  58. 			m[Arr[i]]=x;
  59. 		}
  60. 	}
  61.  
  62. 	for (std::map<int,vector<int> >::iterator it=m.begin(); it!=m.end(); ++it) {
  63. 		vector<int> x = it->second;
  64. 		for(int j=0;j<x.size();++j) {
  65. 			cout<<x[j]<<" ";
  66. 		}
  67. 		cout<<endl;
  68. 	}
  69.  
  70. 	return 0;
  71. }
Success #stdin #stdout 0s 2880KB
comments (?)
stdin 
Standard input is empty
stdout 
1 2 4 
3 5
https://ideone.com/vsT9Jh
language:
C++ 4.3.2 (gcc-4.3.2)
created:
7 years ago
visibility:
secret

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!