Cod sursa(job #2662815)

Utilizator Silviu.Stancioiu@gmail.comSilviu Stancioiu [email protected] Data 24 octombrie 2020 16:03:06
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>

using namespace std;

vector<vector<int>> graph;
vector<int> top_sort_result;
vector<int> in_deg;

void top_sort()
{
    for (const auto& ls : graph)
        for (auto node : ls)
            in_deg[node]++;

    for (unsigned int i = 0; i < in_deg.size(); i++)
        if (in_deg[i] == 0)
            top_sort_result.push_back(i);

    for (unsigned int i = 0; i < top_sort_result.size(); i++)
    {
        for (auto neighbor : graph[top_sort_result[i]])
        {
            in_deg[neighbor]--;
            if (in_deg[neighbor] == 0)
                top_sort_result.push_back(neighbor);
        }
    }
}

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

    unsigned int n, m;
    fin >> n >> m;

    graph = vector<vector<int>>(n, vector<int>());
    in_deg = vector<int>(n, 0);

    for (unsigned int i = 0; i < m; i++)
    {
        int x, y;
        fin >> x >> y;
        x--;
        y--;
        graph[x].push_back(y);
    }

    fin.close();

    top_sort();

    if (top_sort_result.size() == n)
    {
        for (auto node : top_sort_result)
            fout << node + 1 << " ";
    }

    fout.close();

    return 0;
}