Cod sursa(job #720977)

Utilizator hiticas_abelhiticasabel hiticas_abel Data 23 martie 2012 09:17:44
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include<fstream>
#include<vector>
#include<bitset>
using namespace std;

const int maxn=50005;
bitset<maxn>viz;
vector <int>s[maxn];
int n,m,i,x,y,nrm,nr[maxn],coada[maxn];

void df(int kapa)
{

	viz[kapa]=1;
	for(int i=0;i<nr[kapa];i++)
		if(!viz[s[kapa][i]])
			df(s[kapa][i]);
		
		coada[++nrm]=kapa;
}

int main()
{
 ifstream f("sortaret.in");
 ofstream g("sortaret.out");
 
 f>>n>>m;
 for(i=1;i<=m;i++)
    {
	 
		f>>x>>y;
		nr[x]++;
		s[x].push_back(y);
    }

 for(i=1;i<=n;i++)
	 if(!viz[i])
		 df(i);
	 
	 for(i=n;i;i--)
		 g<<coada[i]<<" ";
	 
	 return 0;
 
}