Cod sursa(job #3362286)

Utilizator NFJJuniorIancu Ivasciuc NFJJunior Data 5 august 2026 14:53:01
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<vector<int>> adj;
vector<int> in_degree;

vector<int> topsort()
{
    vector<int> sorted;
    queue<int> q;

    for (int i = 0; i < n; i++) {
        if (in_degree[i] == 0)
            q.push(i);
    }

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        sorted.push_back(node);

        for (int next : adj[node]) {
            if (--in_degree[next] == 0)
                q.push(next);
        }
    }

    return sorted;
}

int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

    cin >> n >> m;
    adj.resize(n);
    in_degree.resize(n);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        adj[--x].push_back(--y);
        in_degree[y]++;
    }

    vector<int> sorted = topsort();
    for (int node : sorted)
        cout << node + 1 << ' ';
    cout << '\n';

    return 0;
}