Cod sursa(job #2124364)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 7 februarie 2018 10:10:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;
vector <int> v[50001];
int grad[50001];
queue <int> q;
int main()
{
    FILE *fin=fopen ("sortaret.in","r");
    FILE *fout=fopen ("sortaret.out","w");
    int n,m,i,nod,vecin,x,y;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(y);
        grad[y]++; // grad[i] = cate arce duc la nodul i
    }
    for (i=1;i<=n;i++){
        if (grad[i]==0) // i nu trb sa se afle dupa niciun alt nod NEAPARAT
            q.push(i);
    }
    while (q.size()!=0){
        nod=q.front();
        q.pop();
        fprintf (fout,"%d ",nod);
        for (i=0;i<v[nod].size();i++){
            vecin=v[nod][i];
            grad[vecin]--; // practic elimin nodul nod din graf, eu la fiecare pas adaug in sortare
            if (grad[vecin]==0) // daca am adaugat toate nodurile care trebuiau sa se afle inaintea lui vecin
                q.push(vecin);
        }
    }
    return 0;
}