Cod sursa(job #672888)

Utilizator federerUAIC-Padurariu-Cristian federer Data 3 februarie 2012 12:58:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<fstream>
#include<vector>
#include<cstring>
#define Nmax 50001
using namespace std;
vector<int> G[Nmax];
int n, m, deg[Nmax], j, q[Nmax];

void solve()
{
	vector<int>:: iterator it;
	int x, i;
	for(i=1;i<=n;i++)
		if(deg[i]==0)
			q[++q[0]]=i;
		
	for(i=1;i<=n;i++)
	{
		x=q[i];
		for(it=G[x].begin();it!=G[x].end();++it)
		{
			deg[*it]--;
			if(deg[*it]==0)
				q[++q[0]]=*it;
		}
	}
}

int main()
{
	int a, b, i;
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	scanf("%d%d\n", &n, &m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d\n", &a, &b);
		G[a].push_back(b);
		deg[b]++;
	}
	solve();
	for(i=1;i<=n;i++)
		printf("%d ", q[i]);
	printf("\n");
	fclose(stdin);
	fclose(stdout);
	return 0;
}