Cod sursa(job #931044)

Utilizator xbogdanBogdan Boamfa xbogdan Data 27 martie 2013 22:47:08
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include "iostream"
#include "fstream"
#include "cstdlib"
#include "stack"
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
stack<int> S;
struct nod {
	int nd;
	nod *next;
};
void dfs(int sursa,nod **a,int n,int *&viz) 
{
	viz[sursa] = 1;
	while(a[sursa])
	{
		int c = a[sursa]->nd;
		if( !viz[c] )
			dfs(c,a,n,viz);
		else 
			a[sursa] = a[sursa]->next;
	}
	S.push(sursa);
}
void sortT(nod **a,int n)
{
	int *viz = (int*)calloc(n+1,sizeof(int));
	for(int i = 1; i < n+1; i++)
	{
		if(!viz[i])
			dfs(i,a,n,viz);
	}
}
void read(nod **&a,int &n)
{
	int nr;
	in >> n >> nr;
	// Alocare matrice
	a = (nod**)calloc(n+1,sizeof(nod*));
	for (int i = 0; i < n+1; ++i)
		a[i] = 0;
	// Citire graf
	for(int i = 0; i < nr; ++i)
	{
		int x,y;
		in >> x >> y;
		nod *p = new nod;
		p->nd = y;
		p->next = a[x];
		a[x] = p;
	}
}
void print(nod **a,int n)
{
	for (int i = 1; i < n+1; ++i)
	{
		cout<<i<<" | ";
		while(a[i])
		{
			cout<<a[i]->nd<<" ";
			a[i] = a[i]->next;
		}
		cout<<"\n";
	}
}
int main(int argc, char const *argv[])
{
	nod **a;
	int n;
	read(a,n);
	//print(a,n);
	sortT(a,n);
	cout<<"\n";
	while(!S.empty())
	{
		cout<<S.top()<<" ";
		S.pop();
	}
	return 0;
}