Pagini recente » Cod sursa (job #2734445) | Cod sursa (job #1749418) | Cod sursa (job #632272) | Cod sursa (job #1806589) | Cod sursa (job #1925570)
//sortare topologica
//kahn alghoritm : se aleg vf care nu mai au tati si se pun intr-o lista;
#include<stdio.h>
#include<vector>
#include<stack>
#define N 50001
using namespace std;
vector <int> v[N];
stack <int> stiv;
int dirin[N];
int sol[N];
int n;
void tsort (){
int i,k,nod;
for (i=1;i<=n;i++)
if (dirin[i] == 0)
stiv.push(i);
k = 0;
while (stiv.empty() == 0){
nod = stiv.top();
stiv.pop();
sol[++k] = nod;
for (i=0;i<v[nod].size();i++){
dirin[v[nod][i]] --;
if (dirin[v[nod][i]] == 0)
stiv.push(v[nod][i]);
}
}
}
int main (){
FILE *in, *out;
in = fopen ("sortaret.in","r");
out = fopen ("sortaret.out","w");
int m,i,n1,n2;
fscanf(in,"%d%d",&n,&m);
for (i=1;i<=m;i++){
fscanf(in,"%d%d",&n1,&n2);
v[n1].push_back(n2);
dirin[n2] ++;
}
tsort ();
for (i=1;i<=n;i++)
fprintf (out,"%d ",sol[i]);
fclose (in);
fclose (out);
return 0;
}