Cod sursa(job #2544730)

Utilizator Vaida_Radu_AndreiVaida Radu Andrei Vaida_Radu_Andrei Data 12 februarie 2020 13:50:09
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>
#include <vector>
#define verticesMax 51024

using namespace std;

int vertices,intG[verticesMax],shown[verticesMax];
vector <int> graph[verticesMax];

void read() {
    int i,edges,v1,v2;
    scanf("%d%d",&vertices,&edges);
    for(i=0;i<edges;++i) {
        scanf("%d%d",&v1,&v2);
        --v1;
        --v2;
        ++intG[v2];
        graph[v1].push_back(v2);
    }
}

void start(int pos) {
    printf("%d ",pos+1);
    ++shown[pos];
    for(auto v:graph[pos]) {
        --intG[v];
        if(!(intG[v]||shown[v])) {
            start(v);
        }
    }
}

void solve() {
    int i;
    for(i=0;i<vertices;++i) {
        if(!(intG[i]||shown[i])) {
            start(i);
        }
    }
}

int main() {
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    read();
    solve();
    return 0;
}