Cod sursa(job #1528210)

Utilizator whoiscrisCristian Plop whoiscris Data 19 noiembrie 2015 11:32:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <utility>
#include <algorithm>

using namespace std;

// MACROS
#define REP(i, a, b) \
	for (int i=int(a); i<=int(b); ++i)


typedef long long int ll;

// vector of int
typedef vector<ll> vi;

// int pair
typedef pair<ll,ll> ii;

// vector of int pairs
typedef vector<ii> vii;

typedef vector<vii> AdjList;

#define N 50001
#define M 100001

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

int n, m, x, y, label;
AdjList adj;
vi sorted, viz;

void read () {
	f >> n >> m;
	adj.resize(n+1, vii());
	viz.resize(n+1, 0);

	REP (i, 1, m) {
		f >> x >> y;
		adj[x].push_back(make_pair(y, 1));
	}
}

void dfs(int u) {
	REP (i, 0, adj[u].size()-1) {
		int v = adj[u][i].first;
		if (!viz[v]) {
			dfs(v);
			viz[v] = 1;
			sorted.push_back(v);
		}
	}
}

void sortaret() {
	REP (i, 1, n) {
		if (!viz[i]) {
			dfs(i);
			viz[i] = 1;
			sorted.push_back(i);
		}
	}
	for (int i=sorted.size()-1; i>=0; --i)
		g << sorted[i] << " ";
}


int main () {

	read();
	sortaret();

	return 0;
}