Cod sursa(job #2796246)

Utilizator AndreeaGeamanuAndreea AndreeaGeamanu Data 7 noiembrie 2021 19:38:24
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

#define nmax 50010

using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");

vector <int> la[nmax];
int sortare_top[nmax], grd_int[nmax]={0};
queue<int> nstart;

void ST(queue<int> nstart){
    int i = 0, nod;
    while (!nstart.empty()){
        sortare_top[i] = nstart.front();
        nod = nstart.front();
        nstart.pop();
        i++;
        for(int j=0; j<la[nod].size(); j++){
            grd_int[la[nod][j]]--;
            if(grd_int[la[nod][j]]==0){
                nstart.push(la[nod][j]);
            }
        }
        la[nod].clear();
    }
}


int main()
{   int n,m,x,y;
    f>>n>>m;
    for(int i=1; i<=m; i++){
        f>>x>>y;
        la[x].push_back(y);
        grd_int[y]++;
    }

    for(int j=1; j<=n; j++){
        if(grd_int[j]==0){
            nstart.push(j);
        }
    }

    ST(nstart);

    for(int k=0; k<n; k++){
        g<<sortare_top[k]<<" ";
    }

    f.close();
    g.close();
    return 0;
}