Cod sursa(job #2796255)

Utilizator AndreeaGeamanuAndreea AndreeaGeamanu Data 7 noiembrie 2021 19:46:16
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 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()){
        // Se ia din coada primul nod si se adauga la solutie
        sortare_top[i] = nstart.front();
        nod = nstart.front();
        nstart.pop();
        i++;
        // Se elimina toate muchiile care pornesc din nodul curent
        for(int j=0; j<la[nod].size(); j++){
        // Se actualizeaza gradul interior pentru fiecare nod unde s-a sters muchia (nod curent, nod)
            grd_int[la[nod][j]]--;
        // Daca gradul interior actualizat este egal cu 0 atunci se adauga in coada
            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;

    // Se introduc muchiile in liste de adiacenta
    for(int i=1; i<=m; i++){
        f>>x>>y;
        la[x].push_back(y);
    // In vectorul grd_int se introduce gradul interior pentru fiecare nod
        grd_int[y]++;
    }

    // In vectorul nstart se pun nodurile cu gradul interior egal cu 0
    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;
}