Cod sursa(job #2763115)

Utilizator tigaieNedelcu Ioan-Andrei tigaie Data 11 iulie 2021 17:11:31
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>
#include <list>
#include <ext/pb_ds/assoc_container.hpp>
#define FOR(i , n) for(int i = 0 ; i < (n) ; i++)
#define N 201
#define apare printf("apare");
#define endl "\n"
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int , int> pii;
const int inf = 1e6;
const int nax = 50001;

vector<int>adj[nax];
vector<bool> visited(nax , false);
vector<int> topologic;

void dfs(int node){
    if(visited[node]) return;
    visited[node] = true;
    for(auto it : adj[node]){
        dfs(it);
    }
    topologic.push_back(node);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    freopen("sortaret.in" , "r" , stdin);
    freopen("sortaret.out" , "w" , stdout);
    int nodes , m;
    cin >> nodes >> m;
    int buffer1 , buffer2;
    FOR(i , m){
        cin >> buffer1 >> buffer2;
        adj[buffer1].push_back(buffer2);
    }
    for(int i = 1 ; i <= nodes ; i++){
        if(!visited[i])
            dfs(i);
    }
    for(int i = topologic.size() - 1 ; i >= 0 ; i--){
        cout << topologic[i] << ' ';
    }
    return 0;
}