Cod sursa(job #2065133)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 13 noiembrie 2017 14:14:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;

vector<vector<int>> adj;
stack<int> st;
const int nmax = 50005;
bool viz[nmax];

void dfs(int root)
{
	viz[root] = true;
	
	for(int i = 0;i < (int) adj[root].size();++i)
	{
		int node = adj[root][i];
		if(!viz[node])
		{
			dfs(node);
		}
	}
	st.push(root);
}

int main()
{
	ifstream in("sortaret.in");
	ofstream out("sortaret.out");
	
	int n, m;
	in >> n >> m;
	adj.resize(n + 1);
	
	for(int i = 0;i < m;++i)
	{
		int x, y;
		in >> x >> y;
		adj[x].push_back(y);
	}
	
	memset(viz, false, sizeof(viz));
	for(int i = 1;i <= n;++i)
	{
		if(!viz[i])
		{
			dfs(i);
		}
	}
	
	while(!st.empty())
	{
		out << st.top() <<" ";
		st.pop();
	}
	in.close();
	out.close();
}