AlenAntonelli

Journey to the moon

Sep 21st, 2017
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 KB | None | 0 0
  1. /// @Alen Gabriel Antonelli, Journey the moon, https://www.hackerrank.com/challenges/journey-to-the-moon
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. struct Grafo
  8. {
  9.     vector <vector <int> > adj;
  10.     vector <bool> visitado;
  11.     vector <int> pais, DP;
  12.  
  13.     int nodos, aristas;
  14.  
  15.     void leer()
  16.     {
  17.         cin >> nodos >> aristas;
  18.         adj.resize(nodos);
  19.         visitado = vector <bool> (nodos, false);
  20.  
  21.         int desde, hasta;
  22.  
  23.         for(int i=0; i<aristas; i++)
  24.         {
  25.             cin >> desde >> hasta;
  26.             adj[desde].push_back(hasta);
  27.             adj[hasta].push_back(desde);
  28.         }
  29.     }
  30.  
  31.     void DFS(int nodo)
  32.     {
  33.         visitado[nodo] = true;
  34.         pais.back()++;
  35.  
  36.         for(int i=0; i<adj[nodo].size(); i++)
  37.             if(!visitado[ adj[nodo][i] ])
  38.                 DFS( adj[nodo][i] );
  39.     }
  40.  
  41.     int censo()
  42.     {
  43.         for (int i=0; i<nodos; i++)
  44.             if( !visitado[i] )
  45.             {
  46.                 pais.push_back(0);
  47.                 DFS(i);
  48.             }
  49.         return pais.size();
  50.     }
  51.  
  52.     unsigned long long maneras_posibles () ///por si las dudas
  53.     {
  54.         unsigned long long cant_posib = 0;
  55.  
  56.         DP = vector <int> ( censo() );
  57.         DP[0] = pais[0];
  58.  
  59.         for (int i=1; i<pais.size(); i++)
  60.             DP[i] = DP[i-1] + pais[i];
  61.  
  62.         for (int i=0; i<DP.size(); i++)
  63.             cant_posib+=pais[i]*(DP.back()-DP[i]);
  64.  
  65.         return cant_posib;
  66.     }
  67. };
  68.  
  69. int main()
  70. {
  71.     Grafo g;
  72.     g.leer();
  73.     cout<<g.maneras_posibles();
  74.  
  75.     return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment