Pagini recente » Cod sursa (job #3121641) | Cod sursa (job #1331049) | Cod sursa (job #1503121) | Cod sursa (job #2141188) | Cod sursa (job #2697839)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("topsort.in");
ofstream fout("topsort.out");
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)
{
fout<<stiva.top() + 1<<" ";
stiva.pop();
}
}
int n, x, y, m;
int main()
{
fin>>n>>m;
Graph g(n);
while(fin>>x>>y)
{
g.addEdge(x-1, y-1);
}
g.topSort();
return 0;
}