Cod sursa(job #3032695)

Utilizator DanyZGH25Maftei Dany Gabriel DanyZGH25 Data 22 martie 2023 16:50:09
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <stack>
using namespace std;
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");
const int N = 50001;
const int M = 100001;

struct element
{
    int vf,urm;
}v[M];


stack <int> stiva;
bool viz[N];
int x,y,nr,lst[N],n,m;

void adauga(int x,int y)
{
    v[++nr].vf = y;
    v[nr].urm = lst[x];
    lst[x] = nr;
}

void dfs(int x)
{
    viz[x]=true;
    for(int p=lst[x];p!=0;p=v[p].urm)
    {
        int y = v[p].vf;
        if(!viz[y])
            dfs(y);
    }
    stiva.push(x);
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        adauga(x,y);
    }
    for(int i=1;i<=n;i++)
        if(!viz[i])
            dfs(i);
    while(!stiva.empty())
    {
        int q = stiva.top();
        stiva.pop();
        cout<<q<<" ";
    }
    return 0;
}