Cod sursa(job #2717859)

Utilizator EckchartZgarcea Robert-Andrei Eckchart Data 8 martie 2021 08:39:56
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include "bits/stdc++.h"
#include <cassert>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<double, double>;
using pld = pair<ld, ld>;
vector<vector<int>> adj;
vector<bool> was_visited;
vector<int> top_sort;


void dfs(const int node)
{
    was_visited[node] = true;

    for (const int adj_node : adj[node])
    {
        if (!was_visited[adj_node])
        {
            dfs(adj_node);
        }
    }
    top_sort.emplace_back(node);
}


int main()
{
    ifstream cin("sortaret.in");
    ofstream cout("sortaret.out");

    int N, M;
    cin >> N >> M;

    was_visited.resize(N + 1), adj.resize(N + 1);
    while (M--)
    {
        int x, y;
        cin >> x >> y;

        adj[x].emplace_back(y);
    }
    
    for (int node = 1; node <= N; ++node)
    {
        if (!was_visited[node])
        {
            dfs(node);
        }
    }

    reverse(begin(top_sort), end(top_sort));
    for (const int node : top_sort)
    {
        cout << node << " ";
    }
}