Cod sursa(job #1595629)

Utilizator qwertyuiTudor-Stefan Berbinschi qwertyui Data 10 februarie 2016 14:04:14
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

vector <int> List, edge[50050];
int N, M, degree[50050];

int main()
{
    fin >>N >>M;

    for (int i = 1; i <= M; ++i)
    {
        int x, y;
        fin >>x >>y;
        edge[x].push_back(y);
        ++degree[y];
    }

    for (int i = 1; i <= N; ++i)
        if (!degree[i])
            List.push_back(i);

    for (int i = 1; i <= N; ++i)
    {
        int current_node;
        current_node = List[i];

        for (int k = 0; k < (int) edge[current_node].size(); ++k)
        {
            --degree[edge[current_node][k]];
            if (!degree[edge[current_node][k]])
                List.push_back(edge[current_node][k]);
        }

    }

    for (int i = 0; i <= List.size(); ++i)
        fout <<List[i] <<' ' ;

    fout <<'\n';

    return 0;
}