Cod sursa(job #1651164)

Utilizator CalarisPredut Denis Stefanita Calaris Data 12 martie 2016 15:00:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>

#define MAX 50008
using namespace std;

vector<int> lst;
bool color[MAX];

struct node
{
    int n;
    node* next;
}*G[MAX];

void DF_TOP(int);
void add(int x,int y);

int main()
{
    fstream f("sortaret.in",ios::in);
    ofstream g("sortaret.out");

    int N,M,i,x,y;
    f>>N>>M;

    for(i=1;i<=M;++i)
        {
        f>>x>>y;
        add(x,y);
        }

    for(i=1;i<=N;++i)
        if(!color[i])
        DF_TOP(i);

    for(i=lst.size()-1;i>=0;--i)
        g<<lst[i]<<" ";

    return 0;
}

void DF_TOP(int nod)
{
   node*q = G[nod];
   color[nod] = 1;
   for(;q!=NULL;q=q->next)
    {
      if(!color[q->n])DF_TOP(q->n);

    }
    lst.push_back(nod);
}

void add(int x,int y)
{
    node* q = new node;
    q->n = y;
    q->next=G[x];
    G[x]=q;
}