Pagini recente » Cod sursa (job #2034064) | Cod sursa (job #2213) | Cod sursa (job #3120690) | Cod sursa (job #2143444) | Cod sursa (job #2697841)
#include <bits/stdc++.h>
using namespace std;
class Graph
{
int V;
list<int> *adj;
void DFS(int start, bool visited[], stack<int> &stiva);
public:
Graph(int V);
void addEdge(int v, int w);
void topSort();
};
Graph::Graph(int V)
{
this -> V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
}
void Graph::DFS(int start, bool visited[], stack<int> &stiva)
{
visited[start] = true;
list<int> :: iterator i;
for(i = adj[start].begin(); i!=adj[start].end(); i++)
if(visited[*i] == false)
DFS(*i, visited, stiva);
stiva.push(start);
}
void Graph::topSort()
{
bool *visited = new bool[V];
for(int i = 0; i<V; i++)
visited[i] = false;
stack<int> stiva;
for(int i = 0; i<V; i++)
if(visited[i] == false)
DFS(i, visited, stiva);
while(stiva.empty() == false)
{
cout<<stiva.top() + 1<<" ";
stiva.pop();
}
}
int n, x, y, m;
int main()
{
cin>>n>>m;
Graph g(n);
for(int i = 1; i<=m; i++)
{
cin>>x>>y;
g.addEdge(x-1, y-1);
}
g.topSort();
return 0;
}