Pagini recente » Cod sursa (job #248276) | Cod sursa (job #1164535) | Cod sursa (job #279003) | Cod sursa (job #2578269) | Cod sursa (job #2664421)
#include <fstream>
#include <vector>
#include <list>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 100010
ifstream f ("sortaret.in");
ofstream g ("sortaret.out");
int n, m;
vector<int> adj[maxn];
int ordering[maxn];
bool visited[maxn];
void dfs(int node, vector<int> &visitedList)
{
visited[node] = true;
for(auto next: adj[node])
{
if(!visited[next])
dfs(next, visitedList);
}
visitedList.push_back(node);
}
void topsort()
{
int i = n;
for(int at = 1; at <= n; at++)
{
if(!visited[at])
{
vector<int> visitedNodes;
dfs(at, visitedNodes);
for(int nodeId: visitedNodes) {
cout << nodeId << " ";
ordering[i] = nodeId;
i--;
}
cout << '\n';
}
}
}
int main()
{
f >> n >> m;
for(int i = 0; i < m; i++)
{
int a, b;
f >> a >> b;
adj[a].push_back(b);
}
topsort();
for(int i = 1; i <= n; i ++)
g << ordering[i] << " ";
return 0;
}