Cod sursa(job #419937)

Utilizator RoCkyRomila RoCky Data 18 martie 2010 10:55:32
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
using namespace std;
int m[500][500];
bool marc[100];
int Q2[120];
int Q[120];
int S[120];
ifstream in("sortaret.in");
ofstream out("sortaret.out");
void recusiv(int x)
{
	if(marc[x]==0)
		marc[x]=1;
	for(i=1;i<=m[x][0];i++)
	{
		
}
int main ()
{
	int x,y,n,i,p,v,li,ls;
	in>>n>>p;
	for(i=0;i<p;i++)
	{
		in>>x>>y;
		m[x][0]++;
		m[x][m[x][0]]=y;
	}
	//for(i=1;i<=n;i++)
	//{
	//	for(v=1;v<=m[i][0];v++)
	//		out<<m[i][v]<<" ";
	//	out<<'\n';
	//}
	//return 0;
	for(i=0;i<n;i++)
		Q[i]=i+1;
	ls = n;
	li = 0;
	bool ok;
	v = 0;
	int li2=0;
	int ls2=0;
	while(li<ls)
	{
		ok = true;
		if(ls2>li2)
		{
			x=Q2[ls2];
			ls2--;
		}
		else
		{
			x=Q[li];
			li++;
			if(marc[x]==1)
				ok = false;
		}
		if(ok){
		S[v++]=x;
		for(i=1;i<=m[x][0];i++)
		{
			if(marc[m[x][i]]==0)
			{
				marc[m[x][i]]=1;
				Q2[++ls2]=m[x][i];
			}
		}
		}
	}
	for(i=1;i<v;i++)
		out<<S[i]<<" ";
	return 0;
}