Cod sursa(job #2802066)

Utilizator andrei.petrisorAndrei Petrisor andrei.petrisor Data 17 noiembrie 2021 14:11:37
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

int N, M, grad[100000], coada[100000];
vector<int> G[100000];

void rezolvare(void) {
    int i, j;
    vector<int>::iterator pointer;

    for (i = 1; i <= N; i++) if (grad[i] == 0) coada[++coada[0]] = i;

    for (j = 1; j <= N; j++) {
        
        i = coada[j];
        for (pointer = G[i].begin(); pointer != G[i].end(); ++pointer) {
            grad[*pointer]--;
            if (grad[*pointer] == 0) coada[++coada[0]] = *pointer;
        }
    }
}


int main()
{
    ifstream f("date.in.txt");
    ofstream g("date.out");
    //citire
    int i, a, b;
    f >> N >> M;
    for (i = 1; i <= M; i++) {
        f >> a >> b;
        G[a].push_back(b);
        grad[b]++;
    }

    rezolvare();

    //afisare
    for (i = 1; i <= N; i++) g << coada[i];

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