Cod sursa(job #634593)

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

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

using namespace std;

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

int main()
{
    vector<int> graph[50001];
    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_back(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 (i = 0; i < graph[u].size(); i++) {
            v = graph[u][i];
            indegree[v]--;
            if (!indegree[v])
                queue.push_front(v);
        }
    }
    
    return 0;
}