Pagini recente » Cod sursa (job #18226) | Cod sursa (job #752416) | Cod sursa (job #2136355) | Cod sursa (job #2181646) | Cod sursa (job #1925507)
//Sortare topologica
// DFS : se coboara pana nu mai exista succesor, si punem nodul in ordine inversa
#include<stdio.h>
#include<vector>
#define N 50001
using namespace std;
vector <int> v[N];
int viz[N];
int sol[N];
int k;
void dfs (int nod){
int i;
viz[nod] = 1;
for (i=0;i<v[nod].size();i++)
if (viz[v[nod][i]] == 0)
dfs (v[nod][i]);
sol[++k] = nod;
}
int main (){
FILE *in, *out;
in = fopen ("sortaret.in","r");
out = fopen ("sortaret.out","w");
int n,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);
}
for (i=1;i<=n;i++)
if (viz[i] == 0)
dfs (i);
for (i=n;i>=1;i--)
fprintf (out,"%d ",sol[i]);
fclose (in);
fclose (out);
return 0;
}