Cod sursa(job #1333081)

Utilizator anaid96Nasue Diana anaid96 Data 2 februarie 2015 19:17:47
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<stdio.h>
#include<vector>

using namespace std;

FILE *in, *out;

//definitions
#define pb push_back

//constants
const int sz = (int) 5e4+1;

//variables
int nodes, edges;
int node1, node2;

vector<int> graph[sz];

bool visited[sz];
int postorder[sz];
int pos;

//functions
void dfs(int node);

int main(void)
{
	in = fopen("sortaret.in","rt");
	out = fopen("sortaret.out","wt");
	
	fscanf(in, "%d%d", &nodes, &edges);
	
	while( edges--)
	{
		fscanf(in, "%d%d", &node1, &node2);
		graph[node1].pb(node2);
	}
	
	for(int i=1; i<=nodes; ++i)
		if(!visited[i])
			dfs(i);
	
	for(int i=nodes; i>=1; --i)
		fprintf(out,"%d ", postorder[i]);
	
	fclose(in);
	fclose(out);
	return 0;
}

void dfs(int node)
{
	visited[node] = true;
	
	vector<int> :: iterator it, end = graph[node].end();
	for( it= graph[node].begin(); it!=end; ++it)
	{
		if(!visited[*it])
			dfs(*it);
	}
	postorder[++pos] = node;
	
}