Cod sursa(job #1007043)

Utilizator otilia_sOtilia Stretcu otilia_s Data 8 octombrie 2013 02:37:40
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <cstdio>
#include <vector>
#include <queue>


using namespace std;
const int NMAX = 50003;

vector<int> G[NMAX], Ginv[NMAX], sol;
int n; 
int deg[NMAX];

void read()
{
	freopen("sortaret.in","r",stdin);
	int m;
	scanf("%d %d\n", &n, &m);
	for (int i = 0; i < m; ++i) {
		int x, y;
		scanf("%d %d", &x, &y);
		G[x].push_back(y);
		Ginv[y].push_back(x);
	}		
}

void solve()
{
	queue<int> Q;
	for (int i = 1; i <= n; ++i) {
		deg[i] = G[i].size();
		if (!deg[i]) {
			Q.push(i);
			sol.push_back(i);
		}
	}
	
	while (!Q.empty()) {
		int x = Q.front();
		Q.pop();
		for (vector<int>::iterator it = Ginv[x].begin(); it!=Ginv[x].end(); ++it) {
			deg[*it]--;
			if (!deg[*it]) {
				Q.push(*it);
				sol.push_back(*it);
			}
		}
	}
}

void print()
{
	freopen("sortaret.out","w",stdout);
	for (int i = n-1; i>=0; i--)
		printf("%d ", sol[i]);
}

int main()
{
	read();
	solve();
	print();
	return 0;
}