Cod sursa(job #3203056)

Utilizator indianu_talpa_iuteTisca Catalin indianu_talpa_iute Data 13 februarie 2024 08:51:31
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>
#define MAXN 50000

using namespace std;

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

int n, m, extdeg[MAXN];
vector<vector<int>> graph;
vector<int> sorted;

int main() {
    fin >> n >> m;
    graph = vector<vector<int>>(n, vector<int>());
    for (int i = 0; i < m; i++) {
        int from, to;
        fin >> from >> to;
        from--, to--;
        graph[from].push_back(to);
        extdeg[to]++;
    }

    for (int i = 0; i < n; i++)
        if (!extdeg[i])
            sorted.push_back(i);
    for (int i = 0; i < n; i++) {
        if (i >= sorted.size())
            return 1;
        int current = sorted[i];
        for (auto neighbour: graph[current]) {
           extdeg[neighbour]--;
           if (!extdeg[neighbour])
               sorted.push_back(neighbour);
        }
    }

    for (auto& node : sorted)
        fout << node + 1 << ' ';
    return 0;
}