Cod sursa(job #989404)

Utilizator gunner_292Mihai Manolescu gunner_292 Data 25 august 2013 16:35:15
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<fstream>
#include<list>

#define dmax 50003

using namespace std;

ifstream in("sortaret.in");
ofstream out("sortaret.out");

int n, m;

list<int> adj[dmax];
list<int> sortedL;

bool visited[dmax];

void dfs(int currentN)
{
    list<int>::iterator it;

    for(it = adj[currentN].begin(); it != adj[currentN].end(); it++)
    {
        if(visited[*it] == false)
        {
            visited[*it] = true;
            dfs(*it);
        }

    }

    sortedL.push_front(currentN);
}


int main()
{
    in>>n>>m;

    for(int i=1; i<=m; i++)
    {
        int a, b;

        in>>a>>b;

        adj[a].push_back(b);
    }
    in.close();

    for(int i=1; i<=n; i++)
        visited[i] = false;

    for(int i=1; i<=n; i++)
    {
        if(visited[i] == false)
            dfs(i);
    }

    list<int>::iterator it;

    for(it = sortedL.begin(); it != sortedL.end(); it++)
        out<<*it<<" ";

    out.close();
    return 0;

}