# include <iostream>
# include <fstream>
# include <list>
void read_data ( std :: istream & , int & ) ;
int ** alloc_matrix ( int ) ;
void free_matrix ( int ** , int ) ;
void print_matrix ( std :: ostream & , int ** , int ) ;
void sortare_topologica ( std :: ostream & , int ** , int ) ;
bool graph_empty ( int ** , int ) ;
void get_start ( int ** , int , std :: list <int> & ) ;
int main () {
std :: ifstream f ("sortaret.in") ;
std :: ofstream g ("sortaret.out") ;
int N ;
int M ;
int x ;
int y ;
int ** matrix ;
read_data ( f , N ) ;
read_data ( f , M ) ;
matrix = alloc_matrix ( N ) ;
for ( int i = 0 ; i < M ; i ++ ) {
read_data ( f , x ) ;
read_data ( f , y ) ;
matrix[x][y] = 1 ;
}
print_matrix ( g , matrix , N ) ;
sortare_topologica ( g , matrix , N ) ;
free_matrix ( matrix , N ) ;
f.close () ;
g.close () ;
return 0 ;
}
void sortare_topologica ( std :: ostream & g , int ** matrix , int N ) {
std :: list <int> solutie ;
std :: list <int> start ;
int ok ;
int node ;
get_start ( matrix , N , start ) ;
while ( ! start.empty () ) {
node = start.front () ;
start.pop_front () ;
solutie.push_back (node) ;
for ( int i = 0 ; i < N ; i ++ ) {
if ( matrix[node][i] == 1 ) {
matrix[node][i] = 0 ;
ok = 1 ;
for ( int j = 0 ; j < N ; j ++ ) {
if ( matrix[j][i] == 1 ) {
ok = 0 ;
break ;
}
}
if ( ok ) {
start.push_back (i) ;
}
}
}
}
if ( graph_empty ( matrix , N ) ) {
g << " Graful are cicluri\n" ;
} else {
for ( std :: list <int> :: iterator it = solutie.begin () ; it != solutie.end () ; ++ it ) {
g << *it << ' ' ;
}
g << '\n' ;
}
}
void get_start ( int ** matrix , int N , std :: list <int> & start ) {
int ok ;
for ( int i = 0 ; i < N ; i ++ ) {
ok = 1 ;
for ( int j = 0 ; j < N ; j ++ ) {
if ( matrix[j][i] == 1 ) {
ok = 0 ;
break ;
}
}
if ( ok ) {
start.push_back (i) ;
}
}
}
bool graph_empty ( int ** matrix , int N ) {
int ok = 1 ;
for ( int i = 0 ; i < N && ok ; i ++ ) {
for ( int j = 0 ; j < N && ok ; j ++ ) {
if ( matrix[i][j] == 1 ) {
ok = 0 ;
}
}
}
return !ok ;
}
void print_matrix ( std :: ostream & g , int ** matrix , int N ) {
for ( int i = 0 ; i < N ; i ++ ) {
for ( int j = 0 ; j < N ; j ++ ) {
g << matrix[i][j] << ' ' ;
}
g << '\n' ;
}
}
int ** alloc_matrix ( int N ) {
int ** matrix ;
matrix = new int * [N] ;
for ( int i = 0 ; i < N ; i ++ ) {
matrix[i] = new int [N] ;
}
return matrix ;
}
void free_matrix ( int ** matrix , int N ) {
for ( int i = 0 ; i < N ; i ++ ) {
delete [] matrix[i] ;
}
delete [] matrix ;
}
void read_data ( std :: istream & f , int & x ) {
f >> x ;
}
Grosu Codrut-Cristian codrut_grosu