Cod sursa(job #3330002)

Utilizator ZsomborZsombor Horvay Zsombor Data 16 decembrie 2025 22:09:51
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream be("sortaret.in");
ofstream ki("sortaret.out");

void dfs(vector<vector<int>> &g, vector<char> &vis, vector<int> &ans, vector<int> &index, int x)
{
    vis[x] = 1;
    ans.push_back(x);
    index[x] = ans.size() - 1;

    for(int i : g[x])
    {
        if(!vis[i])
        {
            dfs(g, vis, ans, index, i);
        }
    }
}

int main()
{
    int n, m;
    be >> n >> m;

    vector<vector<int>> g(n + 1);

    for(int i = 0; i < m; i++)
    {
        int x, y;
        be >> x >> y;

        g[x].push_back(y);
    }

    vector<int> ans;
    vector<char> vis(n + 1);
    vector<int> index(n + 1);
    
    for(int i = 1; i <= n; i++)
    {
        if(!vis[i])
        {
            dfs(g, vis, ans, index, i);
        }
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j : g[i])
        {
            if(index[i] > index[j])
            {
                ans.erase(ans.begin() + index[i]);
                ans.insert(ans.begin() + index[j], i);

                index[i] = index[j];
                index[j]++;

                for(int k = i + 1; k <= j; k++)
                {
                    index[k]++;
                }
            }
        }
    }

    for(int i : ans)
    {
        ki << i << " ";
    }

    return 0;
}