Cod sursa(job #3249233)

Utilizator SilviuC25Silviu Chisalita SilviuC25 Data 15 octombrie 2024 16:52:09
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>
using namespace std;

const int MAX_NUM = 50005;

int n, m;
bitset<MAX_NUM> used;
vector<int> graph[MAX_NUM], degree(MAX_NUM);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        ++degree[b];
    }
    for (int i = 1; i <= n; ++i) {
        if (!used[i] && degree[i] == 0) {
            queue<int> q;
            q.push(i);
            used[i] = true;
            while (!q.empty()) {
                int current = q.front();
                q.pop();
                cout << current << " ";
                for (int node : graph[current]) {
                    --degree[node];
                    if (!used[node] && degree[node] == 0) {
                        used[node] = true;
                        q.push(node);
                    }
                }
            }
        }
    }
    return 0;
}