Cod sursa(job #1961665)

Utilizator andreiudilaUdila Andrei andreiudila Data 11 aprilie 2017 11:40:17
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<fstream>
 using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

int n,uz[50010],v[50010],vf;

struct nod
{
    int val;
    nod *next;
};

typedef nod *lista;

lista l[50010];
void ins(int x,int y)
{
    lista q=new nod;
    q->val=y;
    q->next=l[x];
    l[x]=q;
}
void adauga(int x)
{
    lista q=new nod;
    q->val=x;
    q->next=l[n+1];
    l[n+1]=q;
}

void DFS(int x)
{
    uz[x]=1;
    for(lista p=l[x]; p; p=p->next)
        if(!uz[p->val]) DFS(p->val);
    adauga(x);
}

int main()
{
    int m,x,y,i;

    fin>>n>>m;
    for(i=1; i<=m; ++i) fin>>x>>y,ins(x,y);
    for(i=1; i<=n; ++i)
        if(!uz[i]) DFS(i);
    for(lista p=l[n+1]; p; p=p->next) fout<<p->val<<" ";
    return 0;
}