Cod sursa(job #715428)

Utilizator noobakafloFlorin eu noobakaflo Data 17 martie 2012 11:07:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;

#define MAX_N 50001

int n,m,vizitat[MAX_N];
vector<int> gr[MAX_N],st;


void citeste_graf(void)
{
	freopen("sortaret.in","r",stdin);
	int i,x,y;
	scanf("%d %d",&n,&m);
	for(i=1; i<=m; i++)
	{
		scanf("%d %d",&x,&y);
		gr[x].push_back(y);
	}
	fclose(stdin);
}

void dfs(int nod)
{
	vector<int> ::iterator i;
	vizitat[nod]=1;
	for(i=gr[nod].begin(); i!=gr[nod].end(); i++)
		if(!vizitat[*i])
			dfs(*i);
	st.push_back(nod);
}

void sortare_topologica(void)
{
	int i;
	for(i=1; i<=n; i++)
		if(!vizitat[i])
			dfs(i);
	reverse(st.begin(),st.end());
}

void afiseaza_solutie(void)
{
	freopen("sortaret.out","w",stdout);
	vector<int> ::iterator i;
	for(i=st.begin(); i!=st.end(); i++)
		printf("%d ",*i);
	fclose(stdout);
}

int main()
{
	citeste_graf();
	sortare_topologica();
	afiseaza_solutie();
	return 0;
}