Cod sursa(job #2778507)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 1 octombrie 2021 15:59:18
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>
using namespace std;
 

vector<int> vect[100002];
int grades[100002];

int main() {
 
    int N, M;
 
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");
 
    fin >> N >> M;
    queue<int> q;
 
    int a, b;
    for (int i = 1; i <= M; i++) {
        fin >> a >> b;
        vect[a].push_back(b);
        grades[b]++;
    }
 
    for (int i = 1; i <= N; i++) {
        if (grades[i] == 0) {
            q.push(i);
        }
    }
 
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        for (int j = 0; j < vect[p].size(); j++) {
            grades[vect[p][j]]--;
 
            if (grades[vect[p][j]] == 0) {
                q.push(vect[p][j]);
            }
        }
        fout << p << " ";
    }
 
    return 0;
}