Cod sursa(job #2191370)

Utilizator rrobertBulgaru Robert rrobert Data 2 aprilie 2018 18:01:17
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>
#include <vector>
#include <list>

using namespace std;

vector<int> graph[50001];
list<int> lst;

int N,M,x,y;
int visited[50001];

ifstream in("sortaret.in");
ofstream out("sortaret.out");

void DFS_VISIT(int u) {
	visited[u]=1;

	for (unsigned int v=0;v<graph[u].size();v++)
		if (visited[graph[u][v]]==0)
			DFS_VISIT(graph[u][v]);

	lst.push_front(u);
}

void top_sort() {
	for (int i=1;i<=N;i++) 
		if (visited[i]==0)
			DFS_VISIT(i);
}

int main() {
	in>>N>>M;
	for (int i=0;i<M;i++) {
		in>>x>>y;
		graph[x].push_back(y);
	}

	top_sort();

	for (list<int>::iterator it=lst.begin();it!=lst.end();it++)
		out<<*it<<" ";
	out<<"\n";

	return 0;
}