Cod sursa(job #3168386)

Utilizator AlexandruDrg23Draghici Alexandru AlexandruDrg23 Data 12 noiembrie 2023 12:39:03
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <vector>
#include <set>
#include <fstream>
#include <stack>
using namespace std;

ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");

vector<vector<int>> ma(50001);
vector<int> fina(50001,0);
///vector<int> ince(50001,0);
stack<int> s;
set<pair<int,int>> se;
int timp=0;


void dfs(int nod)
{
    vector<int>::iterator el;
    timp++;
    for(el=ma[nod].begin();el!=ma[nod].end();el++)
    {
        if(fina[*el]==0)
            dfs(*el);
    }
    s.push(nod);
    ++timp;
    fina[nod]=timp;
}

int main()
{
    int n,m;
    fin>>n>>m;
    pair<int,int> p;
    for(int k=1;k<=m;k++)
    {
        fin>>p.first>>p.second;
        if(se.find(p)==se.end())
        {
            ma[p.first].push_back(p.second);
            se.insert(p);
        }
    }
    for(int k=1;k<=n;k++)
    {
        if(fina[k]==0)
            dfs(k);
    }
    while(!s.empty())
    {
        fout<<s.top()<<" ";
        s.pop();
    }
    return 0;
}