Cod sursa(job #2342917)

Utilizator ewaldBerla Ewald ewald Data 13 februarie 2019 15:30:13
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>

#define Nmax 50100

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

struct stack{
      int length=0;
      int elems[Nmax];
        void push( int x ){
        elems [++length] = x;
        }

        int pop(){
        length--;
        return elems[length+1];
        }
};

struct edges{
    int length = 0;
    int neighbours[Nmax] = { 0 };

    int push_neighbour( int x ){
        neighbours[ ++length ] =  x;
    }
};

void recursion (edges e[], bool visited[], stack &s, int poz, int n);
void read_edges (edges e[], int &n, int &m);
void solve(edges e[], bool visited[], stack &s, int n);
void print(stack s);

int main()
{
    bool visited[Nmax] = { 0 };
    stack s;
    edges e[Nmax];
    int n,m;
    read_edges(e,n,m);
    solve(e,visited,s,n);
    print(s);
    return 0;
}

void read_edges (edges e[], int &n, int &m){
    f>>n>>m;
    int a,b;
    for(int i=1;i<=m;i++){
        f>>a>>b;
        e[a].push_neighbour(b);
    }
}

void recursion (edges e[], bool visited[], stack &s, int poz, int n){
   if(poz == n+1)
    return;
   visited[poz] = true;
   for(int i = 1; i<=e[poz].length; i++)
       if( e[poz].neighbours[i]!=0 && !visited[e[poz].neighbours[i]])
           recursion(e,visited,s,e[poz].neighbours[i],n);
   s.push(poz);
}

void solve(edges e[], bool visited[], stack &s, int n){
    for(int i=1; i<=n; i++)
        if(!visited[i]){
            recursion(e,visited,s,i,n);
        }
}

void print(stack s){
  while(s.length){
    g<<s.pop()<<" ";
  }
}