Cod sursa(job #3296238)

Utilizator horia.boeriuBoeriu Horia Andrei horia.boeriu Data 12 mai 2025 11:10:13
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;
#define MAXN 50000
vector<int> v[MAXN + 1];
int grad[MAXN + 1], deq[MAXN];
int main()
{
    FILE *fin, *fout;
    int n, m, i, x, y, nr, pr, ul, nod;
    //se poate si cu parcurgere inversa a vectorului de postordine
    fin = fopen("sortaret.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for (i = 0; i < m; i++) {
        fscanf(fin, "%d%d", &x, &y);
        v[x].push_back(y);
        grad[y]++;
    }
    fclose(fin);
    pr = ul = 0;
    for (i = 1; i <= n; i++) {
        if (grad[i] == 0) {
            deq[ul] = i;
            ul++;
        }
    }
    fout = fopen("sortaret.out", "w");
    while (pr != ul) {
        fprintf(fout, "%d ", deq[pr]);
        nod = deq[pr];
        nr = v[nod].size();
        for (i = 0; i < nr; i++) {
            x = v[nod][i];
            grad[x]--;
            if (grad[x] == 0) {
                deq[ul] = x;
                ul++;
            }
        }
        pr++;
    }
    fclose(fout);
    return 0;
}