Cod sursa(job #993268)

Utilizator pulseOvidiu Giorgi pulse Data 3 septembrie 2013 16:11:53
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#define NMAX 5000

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

int a[750][750],used[100001],n,m,inside[100001],x,y;

bool ok,k;

void read ()
{
	fin>>n>>m;

	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=n; j++)
		{
			a[i][j]=0;
		}
	}

	for (int i=1; i<=m; i++)
	{
		fin>>x>>y;
		a[x][y]=1;
		inside[y]++;
	}
}

void solve ()
{
	ok=false;
	while (!ok)
	{
		k=true; ok=true;

		for (int i=1; i<=n; i++)
		{
			if (!(inside[i]) && k)
			{
				for (int j=1; j<=n; j++)
				{
					if (a[i][j])
					{
						if (inside[j]>=1)
						{
							inside[j]--;
						}
					}
				}
				fout<<i<<" ";
				inside[i]=-1;
				used[i]=1;
				k=false;
			}
			if (used[i]!=1)
			{
				ok=false;
			}
		}
	}
}

int main ()
{
	read ();
	solve ();
	fin.close();fout.close();
	return 0;
}