Cod sursa(job #3181504)

Utilizator Deleanu_LucaDeleanu Luca Deleanu_Luca Data 7 decembrie 2023 08:30:36
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
///BFS
#include <bits/stdc++.h>
#define NMAX 100100

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

queue <int> Q;
vector<int> Gf[NMAX];
int D[NMAX];
int N,M;

void TopSort();

int main()
{
    int i,j,x,y;
    fin>>N>>M;
    for(i=1; i<=M; i++)
    {
        fin>>x>>y;
        Gf[x].push_back(y);
        D[y]++;
    }

    for(i=1; i<=N; i++)
        if(D[i]==0) Q.push(i);

    TopSort();

    return 0;
}

void TopSort()
{
    int x,i,y;
    while(!Q.empty())
    {
        x=Q.front();
        Q.pop();
        fout<<x<<' ';

        for(i=0; i<Gf[x].size(); i++)
        {
            y=Gf[x][i];
            D[y]--;
            if(D[y]==0)
                Q.push(y);
        }
    }
}