Cod sursa(job #1738424)

Utilizator Bulgaru_Robert_Razvan_323CBBulgaru Robert Razvan Bulgaru_Robert_Razvan_323CB Data 6 august 2016 17:43:37
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <list>

using namespace std;

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

vector<int> graph[50003];
list<int> vertices;

unsigned int n,m,x,y;

int visited[50003];

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

	for (unsigned int j=0;j<graph[node].size();j++) {
		if (!visited[graph[node][j]]) {
			DFS_VISIT(graph[node][j]);
		}
	}

	vertices.push_front(node);
}

void DFS(unsigned int n) {
	memset(visited,0,sizeof(visited));

	for (unsigned int i=1;i<=n;i++) {
		if (!visited[i]) {
			DFS_VISIT(i);
		}
	}
}

int main() {
	in>>n>>m;

	for (unsigned int i=1;i<=m;i++) {
		in>>x>>y;
		graph[x].push_back(y);
	}

	DFS(n);

	list<int>::iterator it;
	for (it=vertices.begin();it!=vertices.end();it++) {
		out<<*it<<" ";
	}

	return 0;
}