Cod sursa(job #156386)

Utilizator catalin_olariOlari Catalin Georgel catalin_olari Data 12 martie 2008 15:16:56
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<fstream.h>

int n,m,a[100000][100000];

void citire()
{int x1,x2;
 ifstream f("sortaret.in");
 f>>n>>m;

 for(int i=0;i<m;i++)
	  {f>>x1>>x2;
	   a[x1][x2]=1;
	   }
 f.close();
}


int are_tata(int nod)
{
 for(int i=1;i<=n;i++)
	if(a[i][nod]==1)
		return i;
 return 0;
}


int main()
{int N,i,j,t[100000]={0};
 citire();
 N=n;

 ofstream g("sortaret.out");


 while(N>=1)
 {

 for(i=1;i<=n;i++)
	if(t[i]!=-1)
		t[i]=are_tata(i);
 for(i=n;i>=1;i--)
	if(t[i]==0)
		{g<<i<<" ";
		 t[i]=-1;

		 if(n==i)
			{n--;
			 N--;
			}

		 else
		 {for(j=1;j<=n;j++)
			a[j][i]=a[i][j]=-1;
		  N--;
		  }
		}

}

g.close();

return 0;
}