Cod sursa(job #2594726)

Utilizator radu.millio15Radu Millio radu.millio15 Data 6 aprilie 2020 16:06:28
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda laborator_7_sd_313cab Marime 1.02 kb
#include <stdio.h>
#include <stack>
#include <vector>
#include <string.h>

#define NMAX 50005

using namespace std;

void dfs(int vizitat[], vector<int> G[], int i, stack<int> &stack) {
    vizitat[i] = 1;
    for (int j = 0; j < G[i].size(); j++) {
        int v = G[i][j];
        if (vizitat[v] == 0) {
            dfs(vizitat, G, v, stack);
        }
    }
    stack.push(i);
    return;
}

int main() {
    FILE *fin, *fout; 
    fin = fopen("sortaret.in", "rt");
    fout = fopen("sortaret.out", "wt");
    int n, m;
    fscanf(fin, "%d%d", &n, &m);
    vector<int> G[NMAX];
    for (int i = 0; i < m; i++) {
        int x, y;
        fscanf(fin, "%d%d", &x, &y);
        G[x].push_back(y);
    }
    int vizitat[NMAX]; memset(vizitat, 0, NMAX);
    stack<int> stack;
    for (int i = 1; i <= n; i++) {
        if (vizitat[i] == 0) {
            dfs(vizitat, G, i, stack);
        }
    }
    while (!stack.empty()) {
        fprintf(fout, "%d ", stack.top());
        stack.pop();
    }
    fclose(fin);
    fclose(fout);
    return 0;
}