Cod sursa(job #1103587)

Utilizator gener.omerGener Omer gener.omer Data 9 februarie 2014 20:35:29
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <bitset>
#include <iostream>

using namespace std;

#define INF (1<<29)
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define TIMESTAMP(x) eprintf("["#x"] Time : %.3lf s.\n", clock()*1.0/CLOCKS_PER_SEC)

int n, m;

set<int> out[50005];
int Q[50005], last = 0, in[50005];
	
int main(){
	ifstream fin("sortaret.in");
	ofstream fout("sortaret.out");
	
	fin >> n >> m;
	int x, y;
	for(int i = 0; i < m; ++i)
	{
		fin >> x >> y;
		if(out[x].find(y) == out[x].end())
			out[x].insert(y), in[y]++;
	}
	
	for(int i = 1; i <= n; ++i)
		if(!in[i])
			Q[last++] = i;

	for(int i = 0; i < n; ++i){
		int x = Q[i];
		if(out[x].size()){
			for(set<int>::iterator it = out[x].begin(); it != out[x].end(); ++it) {
				in[*it]--;
				if(!in[*it])
					Q[last++] = (*it);
			}
		}
	}
	
	for(int i = 0; i < n; ++i)
		fout << Q[i] << " ";
	
	return 0;
}