Cod sursa(job #883260)

Utilizator howsiweiHow Si Wei howsiwei Data 19 februarie 2013 21:18:11
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

struct vertex {
	vertex() { ninedge=0; sort=false; }
	int ninedge;
	vector<int> outedge;
	bool sort;
};
vector<vertex> graph;
vector<int> toposort;

void dfs(vertex &v, int ind) {
	if (v.ninedge!=0) return;
	toposort.push_back(ind);
	v.sort=true;
	for (int j=0; j<int(v.outedge.size()); ++j) {
		--graph[v.outedge[j]].ninedge;
		dfs(graph[v.outedge[j]],v.outedge[j]);
	}
}

int main() {
	ifstream fin("test1.in");
	ofstream fout("sortaret.out");
	int n, nedge;
	fin >> n >> nedge;
	graph.resize(n+1);
	for (int i=0,from,to; i<nedge; ++i) {
		fin >> from >> to;
		graph[from].outedge.push_back(to);
		++graph[to].ninedge;
	}
	for (int i=1; i<=n; ++i) {
		if (graph[i].sort || graph[i].ninedge!=0) continue;
		dfs(graph[i],i);
	}
	for (int i=0; i<n; ++i) fout << toposort[i] << ' ';
	return 0;
}