Cod sursa(job #2640197)

Utilizator filip20Comsa Filip filip20 Data 5 august 2020 16:27:41
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int n,m;//nr of nodes
vector<int> g[50100];
int eg[50100]={0};
int q[50100]={0};// queue that has all grades 0


ifstream f("sortaret.in");
ofstream gg("sortaret.out");
void citire_fisier(void )
{

int i,a,b;
for(i=0;i<m;i++)
    {
        f>>a>>b;
        g[a].push_back(b);// for every node we have as value it's thing where it goes
        eg[b]++;//how many nodes does one node have
    }

}
void sortare_topologica(void)
{
  
  int i, x;
  vector<int>:: iterator it;
  
  for(x=0;x<n;x++)
  {
      if(eg[x]==0)
      {
          q[++q[0]]=x;
      }
      for(i=0;i<n;i++)
      {
          x=q[i];
          for( it = g[x].begin();it != g[x].end();++it)
            {
                eg[*it]--;
                if(eg[*it]==0)
                {
                    q[++q[0]]=*it;
                }
                
            }
      }

  }
}


int main()
{
f>>n>>m;
citire_fisier();
sortare_topologica();
for(int i =0;i<n;i++)
    {
        gg<<q[i]<<" ";
    }

}