Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /// @Alen Gabriel Antonelli, Journey the moon, https://www.hackerrank.com/challenges/journey-to-the-moon
- #include <iostream>
- #include <vector>
- using namespace std;
- struct Grafo
- {
- vector <vector <int> > adj;
- vector <bool> visitado;
- vector <int> pais, DP;
- int nodos, aristas;
- void leer()
- {
- cin >> nodos >> aristas;
- adj.resize(nodos);
- visitado = vector <bool> (nodos, false);
- int desde, hasta;
- for(int i=0; i<aristas; i++)
- {
- cin >> desde >> hasta;
- adj[desde].push_back(hasta);
- adj[hasta].push_back(desde);
- }
- }
- void DFS(int nodo)
- {
- visitado[nodo] = true;
- pais.back()++;
- for(int i=0; i<adj[nodo].size(); i++)
- if(!visitado[ adj[nodo][i] ])
- DFS( adj[nodo][i] );
- }
- int censo()
- {
- for (int i=0; i<nodos; i++)
- if( !visitado[i] )
- {
- pais.push_back(0);
- DFS(i);
- }
- return pais.size();
- }
- unsigned long long maneras_posibles () ///por si las dudas
- {
- unsigned long long cant_posib = 0;
- DP = vector <int> ( censo() );
- DP[0] = pais[0];
- for (int i=1; i<pais.size(); i++)
- DP[i] = DP[i-1] + pais[i];
- for (int i=0; i<DP.size(); i++)
- cant_posib+=pais[i]*(DP.back()-DP[i]);
- return cant_posib;
- }
- };
- int main()
- {
- Grafo g;
- g.leer();
- cout<<g.maneras_posibles();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment