Cod sursa(job #2196067)

Utilizator Anastasia11Susciuc Anastasia Anastasia11 Data 18 aprilie 2018 11:55:56
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <vector>
#include <queue>
#define Nmax 50005

using namespace std;

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

int n, m, x, y;
vector <int> v[Nmax];
int nr[Nmax];
queue <int> Q;

void read()
{
    f >> n >> m ;
     while( m -- )
     {
         f >> x >> y;
         v[x].push_back(y);
         nr[y]++;
     }
}

void topologic_bfs()
{
    for ( int i = 1 ; i <= n ; i ++ )
     if( nr[i] == 0 )
       Q.push(i);
     while(!Q.empty())
      {
          int old_node=Q.front();
          Q.pop();
          g << old_node << " ";
           int l = v[old_node].size();
         for ( int i = 0 ; i < l ; i ++ )
          {
              int new_node=v[old_node][i];
              nr[new_node]--;
               if ( nr[new_node] == 0 )
                Q.push(new_node);
          }
      }
}

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