Cod sursa(job #1006656)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 7 octombrie 2013 15:39:22
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

bool t[50005];
int res[50005],rp;
int viz[50005];
int n,m;
queue <int> q;
vector <int> v[50005];

int main() {
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (int i=1;i<=n;i++) {
		int tata,fiu;
		scanf("%d %d",&tata,&fiu);
		v[tata].push_back(fiu);
		t[fiu] = true;
	}
	for (int i=1;i<=n;i++) if (!t[i]) {
		q.push(i);
		viz[i] = true;
		res[++rp] = i;
	}
	while (!q.empty()) {
		int n = q.front(); q.pop();
		while (!v[n].empty()) {
			int nod = v[n].back(); v[n].pop_back();
			if (viz[nod]) continue;
			viz[nod] = true;
			res[++rp] = nod;
			q.push(nod);
		}
	}
	for (int i=1;i<=n;i++) printf("%d ",res[i]);
	return 0;
}