Cod sursa(job #1543058)

Utilizator dragos000Cojanu Dragos dragos000 Data 5 decembrie 2015 21:49:50
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <stack>
#include <fstream>

using namespace std;

stack <int> q;
int m,n,v[100];

 struct nod {
        int val;
        nod * urm;
} *l[100];

void vecini(int x, int y)
{
    nod *p=new nod;
    p->val=y;
    p->urm=l[x];
    l[x]=p;

}

void citire()
{
        ifstream f("sortaret.in");
        f>>n>>m;

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

void df(int i)
{
    v[i] = 1;
    for(nod *p=l[i]; p;p=p->urm)
        if(v[p->val]==0)
              df(p->val);
     v[i]=2;
     q.push(i);
}

void topo()
{
    for(int i=1;i<=n;i++)
        if(v[i]==0)
        df(i);
}





void afisare()
{
    ofstream g("sortaret.out");
    while(!q.empty())
    {
        g<<q.top()<<" ";
        q.pop();
    }
    g.close();

}

int main()
{
    citire();
    topo();
    afisare();
    return 0;
}