Pagini recente » Cod sursa (job #2683146) | Cod sursa (job #1139324) | Cod sursa (job #2943351) | Cod sursa (job #1900085) | Cod sursa (job #1435121)
// Toposort.cpp : Defines the entry point for the console application.
//
#include "stdio.h"
#include "stdlib.h"
#include <iostream>
#include "vector"
#include <fstream>
#include <list>
using namespace std;
vector<int> graph[50005];
bool visited[50005];
list<int> result;
ifstream input("sortaret.in");
ofstream output("sortaret.out");
void dfs_comp(int comp);
void topoSort(int n);
void printRes();
void topoSort(int n)
{
memset(visited, 0, (n + 1) * sizeof(bool));
for (int i = 1; i <= n; i++)
{
if (!visited[i])
dfs_comp(i);
}
}
void dfs_comp(int comp)
{
visited[comp] = true;
for (int i : graph[comp])
{
if (!visited[i])
dfs_comp(i);
}
result.push_front(comp);
}
void printRes()
{
for (list<int>::iterator it = result.begin(); it != result.end(); it++)
{
output << *it << " ";
}
}
int main()
{
int n, m;
input >> n >> m;
int x, y;
for (int i = 0; i < m; i++)
{
input >> x >> y;
graph[x].push_back(y);
}
topoSort(n);
printRes();
input.close();
output.close();
return 0;
}