Cod sursa(job #3264126)

Utilizator gasparrobert95Gaspar Robert Andrei gasparrobert95 Data 18 decembrie 2024 14:57:24
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

vector<int> rez;

void dfs(vector <int> g[], int node, int viz[]) {
    //cout << node << " ";
    viz[node] = 1;
    for (auto next : g[node])
        if (!viz[next])
            dfs(g, next, viz);
    return;
}

void dfsDemo() {
    vector <int> g[5];
    //1 - 2
    g[1].push_back(2);
    g[2].push_back(1);
    //1 - 3
    g[1].push_back(3);
    g[3].push_back(1);
    //2 - 4
    g[2].push_back(4);
    g[4].push_back(2);
    //2 - 3
    g[2].push_back(3);
    g[3].push_back(2);
    for (int i = 1; i <= 4; ++i) {
        cout << i << ": ";
        for (auto node : g[i])
            cout << node << " ";
        cout << "\n";
    }
    int viz[5] = {0};
    dfs(g, 1, viz);
    return;
}

void topSort(vector <int> g[], int node, int viz[]) {
    rez.push_back(node);
    viz[node] = 1;
    for (auto next : g[node])
        if (!viz[next])
            topSort(g, next, viz);
    return;
}

void sortareTopologica() {
    vector <int> g[10];
    g[1].push_back(2);
    g[1].push_back(3);
    g[3].push_back(4);
    g[3].push_back(5);
    g[5].push_back(9);
    g[4].push_back(6);
    g[4].push_back(7);
    g[4].push_back(8);
    int viz[10] = {0};
    for (int i = 1; i <= 9; ++i)
        if (!viz[i])
            topSort(g, i, viz);
    for (auto node : rez)
        cout << node << " ";
    return;
}

int main() {
    //dfsDemo();
    //sortareTopologica();
    int n, m;
    fin >> n >> m;
    int viz[50005] = {0};
    vector <int> g[n + 1];
    while (m--) {
        int a, b;
        fin >> a >> b;
        g[a].push_back(b);
    }
    for (int i = 1; i <= n; ++i)
        if (!viz[i])
            topSort(g, i, viz);
    for (auto node : rez)
        fout << node << " ";
    return 0;
}