Cod sursa(job #2352450)

Utilizator CameliaSSamoilescu Camelia CameliaS Data 23 februarie 2019 12:32:17
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");
vector <int> graph[100005];

int viz[100005];
int n, m;

struct nod{
    int varf;
    nod *urm;
};

nod *lista = NULL;
void citire(){
    f >> n >> m;
    for(int i = 1; i <= m; i ++){
        int a, b;
        f >> a >> b;
        graph[a].push_back(b);
    }
}

void add(int node){
    nod *p = new nod;
    p -> varf = node;
    p -> urm = lista;
    lista = p;
}
void dfs(int node){
    viz[node] = 1;
    long long int lim = graph[node].size();
    for(int i = 0; i < lim; i ++){
        int vecin = graph[node][i];
        if(!viz[vecin])
            dfs(vecin);
    }
    add(node);
}
void Sortare_topologica(){
    for(int i = 1; i <= n; i ++)
        if(!viz[i])
            dfs(i);

}

void Afisare(){
    while(lista != NULL){
        g<< lista -> varf << ' ';
        lista = lista -> urm;
    }
}
int main() {

    citire();
    Sortare_topologica();
    Afisare();
    return 0;
}