Pagini recente » Cod sursa (job #1220207) | Cod sursa (job #1367224) | Cod sursa (job #2703603) | Cod sursa (job #1082537) | Cod sursa (job #2555312)
#include <cstdio>
#include <vector>
#define NMAX 50001
using namespace std;
int v, e; //nr of vertices, nr of edges
int visited[NMAX];
vector <int> graph[NMAX];
vector <int> solution;
void read();
void topologicalSort();
void DFS(int);
void write();
int main() {
read();
topologicalSort();
write();
return 0;
}
void read()
{
freopen("sortaret.in", "r", stdin);
scanf("%d%d", &v, &e);
int x, y;
for (int i = 1; i <= e; i++)
{
scanf("%d%d", &x, &y);
graph[x].push_back(y);
}
}
void topologicalSort()
{
for (int i = 1; i <= v; i++)
{
if (visited[i] == 0)
{
DFS(i);
}
}
}
void DFS(int n)
{
visited[n] = 1;
for (unsigned int i = 0; i < graph[n].size(); i++)
{
int neighbour = graph[n][i];
if (!visited[neighbour])
{
DFS(neighbour);
}
}
solution.push_back(n);
}
void write()
{
freopen("sortaret.out", "w", stdout);
while(!solution.empty())
{
printf("%d ", solution.back());
solution.pop_back();
}
fclose(stdout);
}