Cod sursa(job #3267633)

Utilizator iccjocIoan CHELARU iccjoc Data 11 ianuarie 2025 16:59:23
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
using namespace std;
// O sortare topologica.
vector<int> sortTop(int n, vector<vector<int>> graph, vector<int> gradInt)
{
    queue<int> q;
    vector<int> rs;
    for(int i = 1; i <= n; i++)
    {
        if(gradInt[i] == 0)
            q.push(i);
    }
    while(!q.empty())
    {
        int nd = q.front();
        rs.push_back(nd);
        q.pop();
        for(auto it = graph[nd].begin(); it != graph[nd].end(); it++)
        {
            gradInt[(*it)]--;
            if(gradInt[(*it)] == 0)
            {
                q.push((*it));
            }
        }
    }
    return rs;
}
int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    int n, m; 
    cin >> n >> m;
    vector<vector<int>> graph(n+1);
    vector<int> gradInt(n+1);
    for(int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        gradInt[y]++;
    }
    vector<int> rs = sortTop(n, graph, gradInt);
    for(auto it = rs.begin(); it != rs.end(); it++)
    {
        cout << (*it) << " ";
    }
}