Cod sursa(job #1028368)

Utilizator kassay_akosKassay Akos kassay_akos Data 13 noiembrie 2013 22:08:44
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>
#define DIM 50011

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");
										//d = shows if a node has or not incomming edges
bool s[DIM],d[DIM];						//s = shows if a node is had been visited or not 
vector<int> L[DIM];						//L = the graph
int sol[DIM];							//sol = the solution

void dfs(int nod){
	s[nod] = true;
	for(int i = 0; i < L[nod].size(); i++) 
	{
		if (!s[L[nod][i]])
		{
			dfs(L[nod][i]);
		}
	}
	sol[++sol[0]] = nod;
}

int main(){
	int i, j, n, m, x, y;

	f >> n >> m;

	for(i=1;i<=m;i++)
	{
        f>>x>>y;
        L[x].push_back(y);
        d[y]=true;
    }
 
    for(i = 1; i <= n; i++)
	{
        if(!d[i] && !s[i])
            dfs(i);
    }
	
	
	for(i = n; i > 0 ; i--)
        g<<sol[i]<<" ";
    f.close();
    g.close();
	return 0;
}