Cod sursa(job #748939)

Utilizator zeeboBuzatu Vlad zeebo Data 15 mai 2012 10:43:45
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <cstdio>
#include <vector>
#define pb push_back
using namespace std;

vector <int> gr[200000];
vector <int> :: iterator it;
int ord[200000],nr=0;
bool sel[200000];
void dfs (int x)
{
	vector <int> :: iterator it;
	sel[x]=true;
	for (it=gr[x].begin(); it!=gr[x].end(); it++)
		if (!sel[*it])
			dfs(*it);
 ord[++nr]=x;
}
int main ()
{
freopen ("sortaret.in","r",stdin);
freopen ("sortaret.out","w",stdout);
	int n,m,i,x,y,nc;
   
	scanf("%d%d", &n, &m);
	for (i=1;i<=m;i++)
	{
		scanf("%d%d", &x, &y);
		gr[x].push_back(y);
    }
nc=0;
for (i=1;i<=n;i++)
	if (!sel[i])
	{
		nc++;
		dfs(i);
	}
for (i=1;i<=nr;i++) printf("%d ",ord[nr-i+1]);
return 0;
}