Cod sursa(job #1130304)

Utilizator anaid96Nasue Diana anaid96 Data 28 februarie 2014 12:28:53
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<stdio.h>
#include<vector>

using namespace std;

FILE *in,*out;

//definitii
#define pb push_back

//functii
void dfs(int node);

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

//variabile
int noduri,muchii;
vector<int> graf[Nmax];
vector<int> graft[Nmax];
int nod1,nod2;
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();
	
	for(it=graft[node].begin() ; it!=end ; ++it)
		if(!viz[*it])
			return ;
		
	if(!viz[node])
	{
		viz[node]=true;
		fprintf(out,"%d ",node);
	}
	
	vector<int> :: iterator end2=graf[node].end();
	
	for(it=graf[node].begin() ; it!=end2 ; ++it)
		dfs(*it);
}