Cod sursa(job #1496157)

Utilizator ArkinyStoica Alex Arkiny Data 4 octombrie 2015 15:01:42
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream>
using namespace std;

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

struct Node
{
	Node *next;
	int v;
}*A[50001];

int N, M, v[50001], st[50001], s = 0;

void add_to_graph(int i, int j)
{
	Node *q = new Node;
	q->next = A[i];
	q->v = j;
	A[i] = q;
}


void sort_top(int i)
{
	Node *q = A[i];
	int e;
	while (q)
	{
		e = q->v;
		if (!v[e])
			v[e] = 1, sort_top(e);
		q = q->next;
	}
	st[s++] = i;
}

int main()
{
	in >> N >> M;
	int a, b;
	for (int i = 1;i <= M;++i)
		in >> a >> b,add_to_graph(a, b);

	v[1] = 1;
	sort_top(1);
	for (int i = 2;i <= N;++i)
		if(!v[i])
			sort_top(i);
	--s;
	while (s >= 0)
		out << st[s] << " ", --s;

	in.close();
	out.close();

	return 0;
}