Cod sursa(job #807733)

Utilizator zitu_cuetMuntasir Zitu zitu_cuet Data 5 noiembrie 2012 16:46:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<algorithm>
#include<limits>
#include<vector>
#include<stack>
#include<string>
#include<deque>
#include<list>
#include<bitset>
#include<ctime>
#include<functional>
#include<numeric>
#include<cfloat>
#include<sstream>
#include<complex>
#include<queue>
#include<cstring>
#include<stdexcept>
#include<utility>
#include<map>
#include<fstream>
#include<iomanip>
#include<cassert>
#define MAX(a,b) (a<b?b:a)
#define MIN(a,b) (a<b?a:b)
#define inf (1<<30)-1
#define SIZE 100000001
#define pi 3.14159265358979323846
#define even(a) ((a)%2==0)
#define odd(a) ((a)%2==1)
const double E = 2.7182818284590452353602874713527;
using namespace std;
#define WHITE 0
#define GRAY  1
#define BLACK 2
#define NIL 0
const double eps = 1e-9;
vector<long>vc[100100];
long ind[100100],visit[100100];
queue<long>qu;
stack<long>st;
void dfs(long node)
{
	long i,u,v,p;
	u=node;
		visit[u]=1;
		for(i=0;i<vc[u].size();i++)
		{
			v=vc[u][i];
			if(!visit[v])
			{
			dfs(v);
			}
		}
		st.push(u);
}
int main()
{
	FILE *f1,*f2;
    f1=fopen("sortaret.in","r");
    f2=fopen("sortaret.out","w");
	long test,node,edge,i,j,k,u,v,s;
	fscanf(f1,"%ld%ld",&node,&edge);
		for(i=0;i<edge;i++)
		{
			fscanf(f1,"%ld%ld",&u,&v);
			vc[u].push_back(v);
			ind[v]++;
		}
		for(j=1;j<=node;j++)
		{
			if(ind[j]==0)
			{
				dfs(j);
			}
		}
		k=1;
		while(!st.empty())
		{
			s=st.top();
			if(k>1)
			fprintf(f2," %ld",s);
			else
				fprintf(f2,"%ld",s);
		st.pop();
		vc[s].clear();
		visit[s]=ind[s]=0;
		k++;
		}
		fprintf(f2,"\n");
	fclose(f1);
	fclose(f2);
	return 0;
}