Cod sursa(job #3183856)

Utilizator Dani111Gheorghe Daniel Dani111 Data 13 decembrie 2023 16:26:43
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAX = 100000;
int N, M;
int in_degree[MAX + 3];
int T[MAX + 3], k;
int v[MAX + 3];
vector<int>G[MAX + 3];
queue<int>q;
int X, Y;

void topo() {
    for(int i = 1; i <= N; i++) {
        for(auto j : G[i]) {
            in_degree[j]++;
        }
    }
    for(int i = 1; i <= N; i++) {
        if(in_degree[i] == 0)
        q.push(i);
    }
    while(!q.empty()) {
        T[++k] = q.front();
        for(auto i : G[q.front()]) {
            in_degree[i]--;
            if(in_degree[i] == 0 && !v[i]) {
                v[i] = 1;
                q.push(i);
            }
        }
        q.pop();
    }
}

int main() {
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    cin >> N >> M;
    for(int i = 1; i <= M; i++) {
        cin >> X >> Y;
        G[X].push_back(Y);
    }
    topo();
    for(int i = 1; i <= N; i++) {
        cout << T[i] << ' ';
    }
}