Cod sursa(job #2801264)

Utilizator DayanamdrMardari Dayana Raluca Dayanamdr Data 15 noiembrie 2021 18:38:04
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

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

struct Node {
    vector<int> children;
    int visited = false;

    void add_child(int child_to_add) {
        children.push_back(child_to_add);
    }
} nodes[50001];

void topological_sort(int current_node, vector<int> &topological_sorted_nodes) {
    nodes[current_node].visited = true;
    topological_sorted_nodes.push_back(current_node);
    for (auto child : nodes[current_node].children) {
        if (nodes[child].visited == false) {
            topological_sort(child, topological_sorted_nodes);
        }
    }
}

int main() {
    int n, m;
    f >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        f >> x >> y;
        nodes[x].add_child(y);
    }
    vector<int> topological_sorted_nodes;
    // how do I know which one is the father???
    for (int i = 1; i <= n; ++i) {
        if (nodes[i].visited == false) {
            topological_sort(i, topological_sorted_nodes);
        }
    }
    for (int i = 0; i < n; ++i) {
        g << topological_sorted_nodes[i] << " ";
    }
    return 0;
}