Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <stack>
- using namespace std;
- struct Grafo
- {
- vector <vector <int> > adj;
- vector <bool> v;
- stack <int> orden;
- int nodos, aristas;
- void DFS(int n)
- {
- v[n] = true;
- for(int i=0; i<adj[n].size(); i++)
- if(!v[adj[n][i]])
- DFS(adj[n][i]);
- orden.push(n);
- }
- void leer()
- {
- cin >> nodos >> aristas;
- adj.resize(nodos+1);
- ///adj = vector <vector <int> > (nodos+1, vector <int>());
- v = vector <bool> (nodos+1, false);
- int nodo1, nodo2;
- for(int i=0; i<aristas; i++)
- {
- cin >> nodo1 >> nodo2;
- adj[nodo1].push_back(nodo2);
- ///adj[nodo2].push_back(nodo1); ///Solamente la usamos si es no-dirigido
- }
- }
- void ordenTopologico()
- {
- /**
- DAG -> Directed Acyclic Graph
- **/
- for(int i=0; i<nodos; i++)
- {
- if(!v[i])
- {
- DFS(i);
- }
- }
- while(orden.size())
- {
- cout << orden.top() << endl;
- orden.pop();
- }
- }
- };
- int main()
- {
- Grafo g;
- g.leer();
- g.ordenTopologico();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment