Pagini recente » Cod sursa (job #812858) | Cod sursa (job #2882728) | Cod sursa (job #2970925) | Cod sursa (job #2102881) | Cod sursa (job #1990938)
#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;
}