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. vii edges;
  28. vii addedEdges;
  29.  
  30. int find(int nd){
  31.     if(parent[nd] == nd){
  32.         return nd;
  33.     }
  34.     return parent[nd] = find(parent[nd]);
  35. }
  36.  
  37. void unite(int nd1, int nd2){
  38.     nd1 = find(nd1);
  39.     nd2 = find(nd2);
  40.     if(nd1 == nd2){
  41.         return;
  42.     }
  43.     if(componentSize[nd1] < componentSize[nd2]){
  44.         swap(nd1, nd2);
  45.     }
  46.     parent[nd2] = nd1;
  47.     componentSize[nd1] += componentSize[nd2];
  48. }
  49.  
  50. void query(int nd1, int nd2){
  51.     if(find(nd1) == find(nd2)){
  52.         cout << "SI, la componente tiene "
  53.              << componentSize[find(nd1)] << " nodos" << endl;
  54.     }
  55.     else{
  56.         cout << "NO" << endl;
  57.     }
  58. }
  59.  
  60. void connectGraph(){
  61.     vi representatives;
  62.     ffor(i, 0, 10){
  63.         if(find(i) == i){
  64.             representatives.pb(i);
  65.         }
  66.     }
  67.     ffor(i, 1, sz(representatives)){
  68.         int nd1 = representatives[i - 1];
  69.         int nd2 = representatives[i];
  70.         if(find(nd1) != find(nd2)){
  71.             addedEdges.pb(mp(nd1, nd2));
  72.             unite(nd1, nd2);
  73.         }
  74.     }
  75. }
  76.  
  77. int main()
  78. {
  79.     parent.assign(tam, 0);
  80.     componentSize.assign(tam, 1);
  81.     ffor(i, 0, tam){
  82.         parent[i] = i;
  83.     }
  84.  
  85.     edges.pb(mp(0, 3));
  86.     edges.pb(mp(0, 5));
  87.     edges.pb(mp(3, 6));
  88.     edges.pb(mp(5, 6));
  89.     edges.pb(mp(1, 4));
  90.     edges.pb(mp(4, 8));
  91.     edges.pb(mp(2, 7));
  92.  
  93.     ffor(i, 0, sz(edges)){
  94.         unite(edges[i].F, edges[i].S);
  95.     }
  96.  
  97.     query(5, 3);
  98.     query(1, 8);
  99.     query(6, 7);
  100.     query(9, 9);
  101.  
  102.     connectGraph();
  103.  
  104.     cout << "Se necesitan " << sz(addedEdges)
  105.          << " aristas para conectar todo el grafo:" << endl;
  106.     ffor(i, 0, sz(addedEdges)){
  107.         cout << addedEdges[i].F << "-" << addedEdges[i].S << endl;
  108.     }
  109. }
  110.  
Success #stdin #stdout 0.01s 5344KB
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
Se necesitan 3 aristas para conectar todo el grafo:
0-1
1-2
2-9
https://ideone.com/1vT6nI
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!