Cod sursa(job #206509)

Utilizator piroslPiros Lucian pirosl Data 7 septembrie 2008 12:49:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include<iostream>
#include<fstream>
using namespace std;

struct vert
{
	int num;
	struct vert* link;
};

bool zeroingrade[50001];
struct vert* adj[50001];
int color[50001];
struct vert* sol;

void dfs(int i)
{
	color[i] = 1;
	struct vert* v = adj[i];
	while(v != NULL)
	{
		if(color[v->num] == 0)
			dfs(v->num);
		v = v->link;
	}
	struct vert* solv = new vert();
	solv->num = i;
	solv->link = sol;
	sol = solv;
}

int main(void)
{
	ifstream in("sortaret.in");
	ofstream out("sortaret.out");
	int n,m;
	sol = NULL;
	in >> n >> m;
	for(int i=1; i<=n;++i)
	{
		zeroingrade[i] = true;
		color[i] = 0;
		adj[i] = NULL;
	}
	for(int i=0;i<m;++i)
	{
		int s, d;
		in >> s >> d;
		zeroingrade[d] = false;
		struct vert* v = new vert();
		v->num = d;
		v->link = adj[s];
		adj[s] = v;
	}

	for(int i=1;i<=n;++i)
	{
		if(zeroingrade[i])
		{
			dfs(i);
		}
	}
	struct vert* v = sol;
	while(v != NULL)
	{
		out << v->num << " ";
		v = v->link;
	}
	out << endl;

	in.close();
	out.close();

	// clear
	v = sol;
	while(v != NULL)
	{
		struct vert* tmpv = v;
		v = v->link;
		delete tmpv;
	}

	for(int i=1; i<=n;++i)
	{
		struct vert* v = adj[i];
		while(v != NULL)
		{
			struct vert* tmpv = v;
			v = v->link;
			delete tmpv;
		}
	}

	return 0;
}