Cod sursa(job #2921513)

Utilizator tzancauraganuTzanca Uraganu tzancauraganu Data 31 august 2022 14:26:43
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <vector>

using namespace std;


#define graph vector<vector<int> >


void insert(int x, const graph& G, vector<int>& ans, vector<bool>& in) {
    for (auto y : G[x])
        if (!in[y])
            insert(y, G, ans, in);
    
    in[x] = true;
    ans.push_back(x);
}

void solve_dfs(int N, const graph& G, vector<int>& ans) {
    vector<bool> in(N + 10, false);

    for (int i = 1; i <= N; i++)
        if (!in[i]) {
            insert(i, G, ans, in);
        }
}
    

int main() {
    ifstream f("sortaret.in");
    ofstream g("sortaret.out");

    int N, M;
    f >> N >> M;
    graph G(N + 2);

    for (int i = 0; i < M; i++) {
        int x, y;
        f >> x >> y;
        G[y].push_back(x);
    }

    vector<int> ans;
    solve_dfs(N, G, ans);
    
    //g << ans.size() << '\n';
    for (int x : ans)
        g << x << ' ';
    g << '\n';

    f.close();
    g.close();
    return 0;
}