Cod sursa(job #2476978)

Utilizator Dragos1226Dragos Chileban Dragos1226 Data 19 octombrie 2019 13:40:43
Problema Sortare topologica Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include<bits/stdc++.h>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
const int Nmax = 10000;

vector <int> G[Nmax+5];
int N, M, Use[Nmax+5], Tsort[Nmax+5], k;

void Read() {
    in >> N >> M;

    for (int i = 1, x, y; i <= M; i++) {
        in >> x >> y;
        G[x].push_back(y);
    }
}

void DFS(int Nod) {
    Use[Nod] = 1;

    for (int i = 0; i < G[Nod].size(); i++) {
        int Vecin = G[Nod][i];

        if(!Use[Vecin])
            DFS(Vecin);
    }

    Tsort[k++] = Nod;
}

int main() {
    Read();

    for (int i = 1; i <= N; i++) {
        if(!Use[i])
            DFS(i);
    }

    for (int i = k-1; i >= 0; i--)
        out << Tsort[i] << " ";
}