Cod sursa(job #2207969)

Utilizator Horia14Horia Banciu Horia14 Data 27 mai 2018 17:28:20
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<cstdio>
#include<vector>
#define MAX_N 50000
using namespace std;

vector<int>g[MAX_N+1];
bool used[MAX_N+1];
int f[MAX_N], n, m, k;

void readGraph() {
    int i, x, y;
    FILE* fin = fopen("sortaret.in","r");
    fscanf(fin,"%d%d",&n,&m);
    for(i = 1; i <= m; i++) {
        fscanf(fin,"%d%d",&x,&y);
        g[x].push_back(y);
    }
    fclose(fin);
}

void DFS(int x) {
    used[x] = true;
    for(auto i : g[x])
        if(!used[i])
            DFS(i);
    f[k++] = x;
}

void DFS_master() {
    for(int i = 1; i <= n; i++)
        if(!used[i])
            DFS(i);
}

void topologicalSort() {
    FILE* fout = fopen("sortaret.out","w");
    for(int i = k-1; i >= 0; i--)
        fprintf(fout,"%d ",f[i]);
    fprintf(fout,"\n");
    fclose(fout);
}

int main() {
    readGraph();
    DFS_master();
    topologicalSort();
    return 0;
}