Cod sursa(job #500605)

Utilizator stay_awake77Cangea Catalina stay_awake77 Data 12 noiembrie 2010 16:21:16
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#define pb push_back

using namespace std;

struct point {int inf; point *leg;};

vector<int> a[100001]/*,coada*/;
//vector<int>::iterator it;
int i,n,m,x,y;
bool used[100001];
point *sortate;

void df(int ind)
{
	point *p;
	
	vector<int>::iterator it;

	used[ind]=true;
	for (it=a[ind].begin();it!=a[ind].end();it++)
	{
		if (!used[*it])
			df(*it);
	}

	p=new point;
	p->inf=ind;
	p->leg=sortate;
	sortate=p;
}

int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	for (i=0;i<m;i++)
	{
		scanf("%d%d",&x,&y);
		a[x].pb(y);
	}
	
	memset(used,false,sizeof(used));
	
	for (i=1;i<=n;i++)
		if (!used[i]) df(i);
	/*reverse(coada.begin(),coada.end());
	for (it=coada.begin();it!=coada.end();it++)
		printf("%d ",*it);*/
	
	while (sortate!=NULL)
	{
		printf("%d ",sortate->inf);
		sortate=sortate->leg;
	}
	
	return 0;
}