Cod sursa(job #1105387)

Utilizator anaid96Nasue Diana anaid96 Data 11 februarie 2014 19:23:41
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<stdio.h>
#include<vector>

using namespace std;

FILE *in,*out;

//functii
void dfs(int node);

//constante
const int Nmax=(int) 5e4+1;

//definitii
#define pb push_back

//variabile
int noduri,muchii,nod1,nod2;
vector<int> graf[Nmax];
vector<int> graft[Nmax];
bool viz[Nmax];


int main(void)
{
	in=fopen("sortaret.in","rt");
	out=fopen("sortaret.out","wt");
	
	fscanf(in,"%d%d",&noduri,&muchii);
	
	while(muchii--)
	{
		fscanf(in,"%d%d",&nod1,&nod2);
		graf[nod1].pb(nod2);
		graft[nod2].pb(nod1);
	}	
	for(int i=1; i<=noduri; ++i)
		dfs(i);
	
	fclose(in);
	fclose(out);
	return 0;
}	

void dfs(int node)
{
	if(viz[node])
		return ;
	vector<int> :: iterator it,end=graft[node].end(),end2=graf[node].end();
	for(it=graft[node].begin() ; it!=end ; ++it)
	{
		if(!viz[*it])
			return;
	}
	if(!viz[node])
	{	
		viz[node]=true;
		fprintf(out,"%d ",node);
	}
	for(it=graf[node].begin() ; it!=end2 ; ++it)
	{
		if(!viz[*it])
			dfs(*it);
	}	
}