Cod sursa(job #3249186)

Utilizator SilviuC25Silviu Chisalita SilviuC25 Data 15 octombrie 2024 11:46:58
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
using namespace std;

const int MAX_NUM = 50005;

int n, m;
queue<int> s;
bitset<MAX_NUM> used;
vector<int> graph[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);
    }
    for (int i = 1; i <= n; ++i) {
        if (!used[i]) {
            queue<int> q;
            q.push(i);
            while (!q.empty()) {
                int current = q.front();
                q.pop();
                used[current] = true;
                for (int node : graph[current]) {
                    if (!used[node]) {
                        used[node] = true;
                        q.push(node);
                    }
                }
                s.push(current);
            }
        }
    }
    while (!s.empty()) {
        cout << s.front() << " ";
        s.pop();
    }
    return 0;
}