Cod sursa(job #2964487)

Utilizator Alex_DumitrascuAlex Dumitrascu Alex_Dumitrascu Data 13 ianuarie 2023 09:06:22
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
FILE *fin=fopen("sortaret.in", "r");
FILE *fout=fopen("sortaret.out", "w");
int deg[100005];
vector <int> G[100005];
int Q[100005];
int main()
{
    int n, m;
    fscanf(fin, "%d%d", &n, &m);
    for (int k=1; k<=m; k++) {
        int i, j;
        fscanf(fin, "%d%d", &i, &j);
        deg[j]++;
        G[i].push_back(j);
    }
    for (int k=1; k<=n; k++) {
        if (deg[k]==0) Q[++Q[0]]=k;
    }
    for (int k=1; k<=n; k++) {
        int x=Q[k];
        for (int i=0; i<G[x].size(); i++) {
            int elem=G[x][i];
            deg[elem]--;
            if (deg[elem]==0) Q[++Q[0]]=elem;
        }
    }
    for (int i=1; i<=Q[0]; i++) {
        fprintf(fout, "%d ", Q[i]);
    }
    return 0;
}