Cod sursa(job #1108779)

Utilizator PlatonPlaton Vlad Platon Data 16 februarie 2014 12:50:17
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <stdio.h>
#include <vector>

using std::vector;

#define maxn 50000
#define maxm 100000

vector<int> l, G[maxn];
bool viz[maxn];
int n, m, grad[maxn];

void citire()
{
	freopen("sortaret.in", "r", stdin);

	scanf("%d%d", &n, &m);
	int a,b;
	while(m--)
	{
		scanf( "%d%d", &a, &b);
		G[a].push_back(b);
		grad[b]++;
	}
}

void dfs(int x)
{
	for(int i=0;i<G[x].size();i++)
	{
		viz[G[x][i]]=1;
		grad[G[x][i]]--;
		if(!grad[G[x][i]])
		{
			l.push_back(G[x][i]);
			dfs(G[x][i]);
		}
	}
}

int main()
{
	citire();

	for(int i=1;i<=n;i++)
	{
		if(!viz[i] && grad[i]==0)
		{
			l.push_back(i);
			dfs(i);
		}
	}

	freopen("sortaret.out", "w", stdout);

	for(int i=0;i<l.size();i++)
	{
		printf("%d ", l[i]);
	}

	return 0;
}