fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //toast418
  5. #define ffor(i,o,f)		   for(int i = o; i < f; i++)
  6. #define pb 				   push_back
  7. #define mp                 make_pair
  8. #define all(a)             (a).begin(), (a).end()
  9. #define F                  first
  10. #define S                  second
  11. #define PI 				   3.14159265358979323846264338327950
  12. #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  13. #define endl 			   '\n'
  14. #define sz(x)              ((int)(x).size())
  15. typedef long long          ll;
  16. typedef pair < int, int >  pii;
  17. typedef vector < int >     vi;
  18. typedef vector < pii >     vii;
  19. typedef vector < vi > 	   gi;
  20. typedef vector < ll >      vll;
  21. typedef map < int, int >   mii;
  22.  
  23. int t, n, m, u, v, groups;
  24. const int tam = 1005;
  25. vi parent;
  26. vi componentSize;
  27.  
  28. int find(int nd){
  29.     if(parent[nd] == nd){
  30.         return nd;
  31.     }
  32.     return parent[nd] = find(parent[nd]);
  33. }
  34.  
  35. void unite(int nd1, int nd2){
  36.     nd1 = find(nd1);
  37.     nd2 = find(nd2);
  38.     if(nd1 == nd2){
  39.         return;
  40.     }
  41.     if(componentSize[nd1] < componentSize[nd2]){
  42.         swap(nd1, nd2);
  43.     }
  44.     parent[nd2] = nd1;
  45.     componentSize[nd1] += componentSize[nd2];
  46. }
  47.  
  48. void query(int nd1, int nd2){
  49.     if(find(nd1) == find(nd2)){
  50.         cout << "SI, la componente tiene "
  51.              << componentSize[find(nd1)] << " nodos" << endl;
  52.     }
  53.     else{
  54.         cout << "NO" << endl;
  55.     }
  56. }
  57.  
  58. int main()
  59. {
  60.     parent.assign(tam, 0);
  61.     componentSize.assign(tam, 1);
  62.     ffor(i, 0, tam){
  63.         parent[i] = i;
  64.     }
  65.  
  66.     unite(0, 3);
  67.     unite(0, 5);
  68.     unite(3, 6);
  69.  
  70.     unite(1, 4);
  71.     unite(4, 8);
  72.  
  73.     unite(2, 7);
  74.  
  75.     query(5, 3);
  76.     query(1, 8);
  77.     query(6, 7);
  78.     query(9, 9);
  79. }
  80.  
Success #stdin #stdout 0s 5348KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
SI, la componente tiene 4 nodos
SI, la componente tiene 3 nodos
NO
SI, la componente tiene 1 nodos
https://ideone.com/tEKCEX
language:
C++14 (gcc 8.3)
created:
1 day 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!