Pagini recente » Rating nabil. (N.B.L) | Cod sursa (job #1606844) | Cod sursa (job #446443) | Cod sursa (job #2764792) | Cod sursa (job #370554)
Cod sursa(job #370554)
/*
Se da un graf orientat. Sa se sorteze topologic graful.
Se numeste sortare topologica o aranjare a nodurilor, cu prop. ca daca exista arcul (i,j) atunci i este in aranjare inaintea lui j.
*/
#include <fstream>
#include <iostream>
using namespace std;
#define MAX 50001
int n, lista[MAX],nrLista, v[MAX];
struct nod{
int info; nod * next;
};
nod * a[MAX];
void read();
void write();
void sort();
void dfs(int varf);
int main(){
read();sort();write();
return 0;
}
void read(){
ifstream fin("sortaret.in");
int m;
fin>>n>>m;
for(int i= 1; i<=n ; ++i)
a[i] = NULL;
for( ; m ; m--){
int i,j;
fin>>i>>j;
nod * p = new nod;
p -> info = j;
p -> next = a[i];
a[i] = p;
}
}
void write(){
ofstream fout("sortaret.out");
for(int i=n;i;--i)
fout<<lista[i]<<" ";
}
void sort(){
for(int i=1;i<=n;i++)
if(!v[i])
dfs(i);
}
void dfs(int varf){
//cout<<varf<<" ";
v[varf] = 1;
for(nod *p = a[varf]; p ; p = p->next){
if(!v[p->info])
dfs(p->info);
}
lista[++nrLista] = varf;
}