Cod sursa(job #144444)

Utilizator GulyanAlexandru Gulyan Data 27 februarie 2008 17:44:50
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<fstream>  
#include<stdio.h> 

using namespace std; 

int c[50000][50000];
int v[100000];
int n,m;

void combsort(int *v, int n)
{
	int gap = n;
	int sort;
	int i;
	int aux;
	do
	{
		gap /=1.3;
		if(gap==9||gap==10)gap=11;
		sort = 1;
		for(i=0;i<n-gap;i++)
		{
			if(c[v[i+gap]][v[i]])
			{
				aux = v[i+gap];
				v[i+gap] = v[i];
				v[i] = aux;
				sort = 0;
			}
		}
	}while(sort==0||gap>1);
}

int main()   
{   
ifstream f1("sortaret.in"); 
ofstream f2("sortaret.out");    

int i, x, y;
f1>>n>>m;
for(i=0;i<m;i++)
{
	f1>>x;
	f1>>y;
	c[x][y] = 1;
}

for(i=0;i<n;i++)v[i]=i+1;

combsort(v,n);

for(i=0;i<n;i++)f2<<v[i]<<' ';

f1.close();
f2.close();

return 0;}