Cod sursa(job #2223308)

Utilizator primeBasso Nicolae prime Data 19 iulie 2018 18:27:08
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <vector>
#include <fstream>

#define f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

int n, m, v[50010], c;						//v - visited(0(unmarked) or 1(marked) or 2(permanent)), c - count of unmarked nodes
vector < int > ft[100010];
vector < int > ans;

void dfs(int x){
	if(v[x] == 2)
		return;
	if(v[x] == 1)
		cout << "Impossible"; 	
		
	for(auto a: ft[x])
		dfs(a);
		
	v[x] = 2;
	ans.pb(x);
}

int main(){
	//freopen("input.txt", "r", stdin);
	ifstream cin("sortaret.in");
	ofstream cout("sortaret.out");
	
	int i, a, b;
	
	cin >> n >> m;
	
	c = n;
	
	for(i = 0; i < m; i++){
		cin >> a >> b;
		
		ft[a].pb(b);
	}
	
	for(i = 1; i <= n; i++)
		if(v[i] == 0)
			dfs(i);
		
	for(i = ans.size() - 1; i >= 0; i--)
		cout << ans[i] << " ";
	
	return 0;
}