Cod sursa(job #2424521)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 23 mai 2019 10:41:45
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
using namespace std;

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

const int NMAX=100005;

int n,m,x,y,viz[NMAX];
int S[NMAX],top;

struct nod
{
    int val;
    nod *next;
}*L[NMAX];

void inserare(nod *&prim , int x)
{
    nod *p=new nod;

    p->val=x;
    p->next=prim;

    prim=p;
}

void read()
{
    fin>>n>>m;

    for(int i=1;i<=m;++i)
    {
        fin>>x>>y;

        inserare(L[x],y);
    }
}

void dfs(int x)
{
    viz[x]=1;

    nod *p;

    for(p=L[x];p;p=p->next)
        if(!viz[p->val]) dfs(p->val);

    S[++top]=x;
}

void topo()
{
    for(int i=1;i<=n;++i)
        if(!viz[i]) dfs(i);

    for(int i=top;i>=1;--i) fout<<S[i]<<" ";
}

int main()
{
    read();
    topo();
    return 0;
}