Cod sursa(job #1599374)

Utilizator qwertyuiTudor-Stefan Berbinschi qwertyui Data 13 februarie 2016 20:09:17
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
//With DF & Linked Lists

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

#define MAXN 50050

vector <int> edge[MAXN];
vector <int> solution;
int used[MAXN], height[MAXN];

int N,M;

void DF(int node)
{
	used[node] = 1;
	for (int i = 0; i < edge[node].size(); ++i)
		if (!used[edge[node][i]])
			DF(edge[node][i]);
	solution.push_back(node);
}


int main()
{
    fin >>N >>M;
    for (int i = 0; i < M; ++i)
	{
		int x,y;
		fin >>x >>y;
		edge[x].push_back(y);
		++height[y];
	}

	for (int i = 1; i <= N; ++i)
		if (!height[i])
			DF(i);

	for (int i = solution.size()-1; i >= 0; --i)
		fout <<solution[i] <<' ';
	fout <<'\n';

    return 0;
}