Cod sursa(job #1990938)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 14 iunie 2017 12:50:21
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>

using namespace std;

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

typedef struct vecin{
  int val;
  vecin * urm;
}NOD;

int n, m, gradInter [ 50001 ], coada[ 50001 ];
NOD *v[ 50001 ];

void initializareArray(){
  for(int i = 1; i <= n; i++){
    v[ i ] = new NOD;
    v[ i ] -> urm = NULL;
  }
}

void citire(){
  in >> n >> m;
  initializareArray();
  for(int i = 1; i <= m; i++){
    int temp1, temp2;
    in >> temp1 >> temp2;//citire capete segment

    gradInter [ temp2 ] ++;//incrementare grad interior

    NOD * aux = new NOD;
    aux -> val =  temp2;
    aux -> urm = v[ temp1 ] -> urm;
    v[ temp1 ] -> urm = aux;//adaugare in array de liste

  }
}

//in coada se pun valorile care au gradul interior 0 , adica nu depind de altcineva
void initializareeCoada(){
  for( int i = 1; i <= n; i++)
    if(gradInter[ i ] == 0)
      coada[ ++ coada[ 0 ] ] = i;
}

void sortaret(){
  initializareeCoada();

  //cat timp coada nu am n elemente in coada, nu le-am sortat top. pe toate
  //parcurg cate un nod care e ndependent, si scot legaturile acestuia cu celel. noduri
  for(int i = 1; i <= coada[ 0 ]; i++){
    NOD * aux = new NOD;
    aux = v [ coada [ i ] ] -> urm;//parcurgem vecinii
    while(aux != NULL){
      gradInter[ aux -> val] -- ;//scad gradul interior
      if(gradInter[ aux -> val ] == 0)
        coada[ ++ coada[ 0 ]] = aux -> val;//adaug in coada nodurile independente
      aux = aux -> urm;//mergem la vecinul urmator
    }
  }
}

void afisare(){
  for(int i = 1; i <= coada[ 0 ]; i++)
    out << coada [ i ] << ' ';
}

int main(){
  citire();
  sortaret();
  afisare();
  return 0;
}