Pagini recente » Cod sursa (job #246839) | Cod sursa (job #1576022) | Cod sursa (job #1984522) | Cod sursa (job #375602) | Cod sursa (job #1978736)
#include <cstdio>
#include <vector>
#include <algorithm>
#define DIMN 50005
FILE *f=fopen("sortaret.in","r"), *g=fopen("sortaret.out","w");
using namespace std;
int N, M, d[DIMN], Q[DIMN]; // d = gradul interior (cate intra)
vector <int> v[DIMN];
void Citire(){
int i, x, y;
fscanf(f,"%d %d\n",&N,&M);
for(i=1;i<=M;i++){
fscanf(f,"%d %d\n",&x,&y);
v[x].push_back(y);
d[y] ++;
}
}
void SortareTopologica(){
int i, k1, k2, NOD, vNOD;
k1 = 1;
k2 = 0;
for(i=1;i<=N;i++) // Pun nodurile cu grad intern 0
if( d[i] == 0 )
Q[++k2] = i;
while( k1 <= k2 ){
NOD = Q[k1++];
for(i=0;i<v[NOD].size();i++){
vNOD = v[NOD][i];
d[vNOD] --;
if( d[vNOD] == 0 )
Q[++k2] = vNOD;
}
}
for(i=1;i<=N;i++)
fprintf(g,"%d ",Q[i]);
}
int main(){
Citire();
SortareTopologica();
return 0;
}