Cod sursa(job #196594)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 27 iunie 2008 13:57:30
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <cstdio>
#include <vector>  
#define IN "sortaret.in"
#define OUT "sortaret.out"
#define N_MAX 1<<16
#define M_MAX 1<<17
#define pb push_back
#define FOR(i,a,b) for(int i=a;i<=b;++i)

using namespace std;
vector < vector <int> > a(N_MAX);

int n,m;
int muchii[N_MAX];
bool viz[N_MAX];

void scan()
{
	int x,y;
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d%d\n", &n,&m);
	FOR(i,1,m)
		scanf("%d%d\n", &x,&y),
		++muchii[y],
		a[x].pb(y);
}

void solve()
{
	int ok,first=1;
	FOR(i,1,n)
	{
		ok=0;
		FOR(j,first,n)
		{
			if(!ok && !viz[j])
				ok=1,first=j;
			if(!viz[j] && !muchii[j])
			{
				//first=j;
				printf("%d ",j);
				viz[j]=1;
				int l=a[j].size();
				FOR(k,0,l-1)
					--muchii[a[j][k]];
				break;
			}
		}
	}	
}

int main()
{
	scan();
	solve();
	return 0;
}