Pagini recente » Cod sursa (job #2279590) | Cod sursa (job #1466073) | Cod sursa (job #1514569) | Cod sursa (job #2731098) | Cod sursa (job #365531)
Cod sursa(job #365531)
/*
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>
using namespace std;
#define MAX 50001
int grad[MAX], n, coada[MAX], v[MAX];
struct nod{
int info; nod * next;
};
nod * a[MAX];
void read();
void write();
void sort();
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;
grad[j]++;
nod * p = new nod;
p -> info = j;
p -> next = a[i];
a[i] = p;
}
}
void write(){
ofstream fout("sortaret.out");
for(int i=1;i<=n;i++)
fout<<coada[i]<<" ";
}
void sort(){
int dr=0,st=1;
for(int i =1 ; i <= n ;i++)
if(grad[i] == 0)
coada[++dr] = i;
while(st<=dr){
int k = coada[st];
for(nod * p = a[k]; p ; p = p->next){
int j = p->info;
grad[j] --;
if(grad[j] == 0)
coada[++dr] = j;
}
st++;
}
}