Cod sursa(job #560949)

Utilizator skullLepadat Mihai-Alexandru skull Data 18 martie 2011 19:23:54
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <stdio.h>
#include <vector>
using namespace std;
#define nmax 50005

vector<int> G[nmax];
int ord[nmax], viz[nmax];
int N, Ncnt;

void citire ()
{
	int i, M, x, y;
	scanf("%d%d", &N, &M);
	for (i = 1; i <= M; ++i)
	{
		scanf("%d%d", &x, &y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	Ncnt = N;
}

void dfs( int nod )
{
	int i, urm;
	viz[nod] = 1;
	for (i = 0; i < G[nod].size (); ++i)
	{
		urm = G[nod][i];
		if ( !viz[urm] ) dfs(urm);
	}
	ord[Ncnt--] = nod;
}

void solve ()
{
	int i;
	for (i = 1; i <= N; ++i)
		if ( !viz[i] ) dfs(i);
	for (i = 1; i <= N; ++i) printf("%d ", ord[i]);
}

int main ()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	citire ();
	solve ();
	return 0;
}