Cod sursa(job #2640328)

Utilizator filip20Comsa Filip filip20 Data 6 august 2020 02:31:24
Problema Sortare topologica Scor 100
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];// queue that has all grades 0


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

void citire_fisier(void )
{

int i,a,b;
for(i=1;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=1;x<=n;x++)
      if(eg[x]==0)
          q[++q[0]]=x;// introducem in  listpe rand elementele 
      
  
    for(i=1;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; //*it  to take the alue of the it 
            }
        }
    }
}


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

}