GastonFontenla

Untitled

Jul 3rd, 2017
153
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.31 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4.  
  5. using namespace std;
  6.  
  7. struct Grafo
  8. {
  9.     vector <vector <int> > adj;
  10.     vector <bool> v;
  11.     stack <int> orden;
  12.         int nodos, aristas;
  13.  
  14.     void DFS(int n)
  15.     {
  16.         v[n] = true;
  17.  
  18.         for(int i=0; i<adj[n].size(); i++)
  19.             if(!v[adj[n][i]])
  20.                 DFS(adj[n][i]);
  21.  
  22.         orden.push(n);
  23.     }
  24.  
  25.     void leer()
  26.     {
  27.  
  28.         cin >> nodos >> aristas;
  29.  
  30.         adj.resize(nodos+1);
  31.         ///adj = vector <vector <int> > (nodos+1, vector <int>());
  32.         v = vector <bool> (nodos+1, false);
  33.  
  34.         int nodo1, nodo2;
  35.  
  36.         for(int i=0; i<aristas; i++)
  37.         {
  38.             cin >> nodo1 >> nodo2;
  39.             adj[nodo1].push_back(nodo2);
  40.             ///adj[nodo2].push_back(nodo1); ///Solamente la usamos si es no-dirigido
  41.         }
  42.     }
  43.  
  44.     void ordenTopologico()
  45.     {
  46.         /**
  47.         DAG -> Directed Acyclic Graph
  48.         **/
  49.  
  50.         for(int i=0; i<nodos; i++)
  51.         {
  52.             if(!v[i])
  53.             {
  54.                 DFS(i);
  55.             }
  56.         }
  57.  
  58.         while(orden.size())
  59.         {
  60.             cout << orden.top() << endl;
  61.             orden.pop();
  62.         }
  63.  
  64.     }
  65. };
  66.  
  67. int main()
  68. {
  69.     Grafo g;
  70.     g.leer();
  71.     g.ordenTopologico();
  72.  
  73.     return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment