Cod sursa(job #2671303)

Utilizator antonioganea3Antonio Ganea antonioganea3 Data 11 noiembrie 2020 21:36:32
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

#define MAXN 100002

vector<int> links[MAXN];
vector<int> output;
bool visited[MAXN];

void dfs(int node){
    if(visited[node])
        return;
    visited[node] = true;
    for(auto v : links[node])
        dfs(v);
    output.push_back(node);
}


int main(){
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");

    int N, M;
    fin >> N >> M;

    int a, b;

    for( int i = 0; i < M; i++ ){
        fin >> a >> b;
        links[a].push_back(b);
    }
    for( int i = 1; i <= N; i++ )
        if(!visited[i])
            dfs(i);

    for( int i = N - 1; i >= 0; i-- )
        fout << output[i] << " ";

    return 0;
}