Cod sursa(job #758433)

Utilizator iris88Nagy Aliz iris88 Data 15 iunie 2012 17:20:11
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <cstdio>
#include <iostream>
#include <fstream>
#include <list>
#include <limits.h>
#include <stdio.h>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stdio.h>
#include <algorithm>
#include <deque>
#include <string.h>
#define NMAX 50001
#define MMAX 100001
using namespace std;
vector<int> G[NMAX];
deque<int> topo_sort;
vector<bool> visited(NMAX);
int poz;


void dfs_visit(int i)
{
	visited[i] = 1;
	for (int j=0;j<G[i].size();j++)
	{
		int v = (G[i]).at(j);
		if (!visited[v]){
			dfs_visit(v);
		}
	}
	topo_sort.push_front(i);	
}
void dfs(int n)
{
	topo_sort.clear();
	poz = n;
	for (int i=1;i<=n;i++)
	{
		visited[i]=0;
	}
	for (int i=1;i<=n;i++)
	{
		if (!visited[i])
		{
			dfs_visit(i);	
		}
	}
}
int main()
{
	FILE* f =  fopen("sortaret.in","r");
	FILE* g = fopen("sortaret.out","w+");
	int n,m;
	fscanf(f,"%d %d",&n, &m);
	for (int i=0;i<m;i++)
	{
		int a,b;
			fscanf(f,"%d %d",&a,&b);
			G[a].push_back(b);
	}
	dfs(n);
	for (deque<int>::iterator it=topo_sort.begin();it!=topo_sort.end();it++)
	{
		fprintf(g,"%d ",(*it));
	}
	fprintf(g,"\n");
	fclose(f);
	fclose(g);
}