Cod sursa(job #185511)

Utilizator tvladTataranu Vlad tvlad Data 25 aprilie 2008 16:22:17
Problema Sortare topologica Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int N = 1000;

int n,m;
vector<int> g[N];
int grad[N];
bool used[N];

void sortare_topologica ( vector<int> &sortt ) {
	queue<int> q;
	for (int i = 0; i < n; ++i)
		if (grad[i] == 0)
			q.push(i);
	for (; !q.empty(); q.pop()) {
		sortt.push_back(q.front());
		used[q.front()] = true;
		for (vector<int>::iterator next = g[q.front()].begin(); next != g[q.front()].end(); ++next) {
			--grad[*next];
			if (grad[*next] == 0)
				q.push(*next);
		}
	}
}

int main() {
	freopen("sortaret.in","rt",stdin);
	freopen("sortaret.out","wt",stdout);
	scanf("%d %d",&n,&m);
	for (int i = 0; i < m; ++i) {
		int a,b;
		scanf("%d %d",&a,&b);
		--a; --b;
		g[a].push_back(b);
		++grad[b];
	}
	
	vector<int> sortt;
	sortare_topologica(sortt);
	
	for (int i = 0; i < n; ++i) printf("%d ",sortt[i]+1);
	printf("\n");
}