Cod sursa(job #634566)

Utilizator fmanceFelix Gabriel Mance fmance Data 16 noiembrie 2011 18:00:37
Problema Sortare topologica Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <list>

#define FILEIN "sortaret.in"
#define FILEOUT "sortaret.out"

using namespace std;

list<int> graph[50001];
int indegree[50001];
deque<int> queue; 

int main()
{
    list<int> graph[50001];
    list<int>::iterator lIter;
    int n, m, i, n1, n2, u, v;
    ifstream f(FILEIN);
    ofstream g(FILEOUT);
    
    f >> n;
    f >> m;
    for (i = 1; i <= m; i++) {
        f >> n1;
        f >> n2;
        graph[n1].push_front(n2);
        indegree[n2]++;
    }
    for (i = 1; i <= n; i++)
        if (!indegree[i])
            queue.push_front(i);
            
    while (!queue.empty()) {
        u = queue.front();
        queue.pop_front();
        g << u << endl;
        for (lIter = graph[u].begin(); lIter != graph[u].end(); lIter++) {
            v = *lIter;
            indegree[v]--;
            if (!indegree[v])
                queue.push_front(v);
        }
    }
    
    return 0;
}