Cod sursa(job #1952888)

Utilizator horiainfoTurcuman Horia horiainfo Data 4 aprilie 2017 14:22:55
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <vector>

#define INF 100001
using namespace std;

ofstream fout("sortaret.out");

struct Node { bool viz, hasInEdges; vector<int> v; };

Node node[50001];
int nr, n, m, v[50001];

void Add(int nod)
{
	node[nod].viz = 1;
	for (int i = 0; i < node[nod].v.size(); i++)
		if (!node[node[nod].v[i]].viz)
			Add(node[nod].v[i]);
	
	v[++nr] = nod;
}

int main() 
{
	freopen("sortaret.in", "r", stdin);
	scanf("%d%d", &n, &m);

	for (int i = 1; i <= m; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		node[x].v.push_back(y);
		node[y].hasInEdges = 1;
	}

	for (int i = 1; i <= n; i++)
		if (!node[i].viz && !node[i].hasInEdges)
			Add(i);

	for (int i = n; i >= 1; i--)
		fout << v[i] << ' ';

	return 0;
}