Cod sursa(job #2675908)

Utilizator LittleGreenMenMihai A LittleGreenMen Data 22 noiembrie 2020 20:24:48
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>
#include <queue>

#define MAX_N 50005

using namespace std;

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

int N, M;
int in_grad[MAX_N];

vector <int> G[MAX_N];
vector <int> Lista;
queue  <int> Q;

int main()
{
    int i, x, y;

    in >> N >> M;
    for(i = 0; i < M; i++) {
        in >> x >> y;

        G[x].push_back(y);
        in_grad[y]++;
    }

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

    while(!Q.empty()) {
        int Nod = Q.front(); Q.pop();
        Lista.push_back(Nod);

        for(i = 0; i < G[Nod].size(); i++) {
            int Vecin = G[Nod][i];

            in_grad[Vecin]--;
            if(in_grad[Vecin] == 0)
                Q.push(Vecin);
        }

        G[Nod].clear();
    }

    for(i = 0; i < Lista.size(); i++)
        out << Lista[i] << ' ';

    in.close();
    out.close();

    return 0;
}