Pagini recente » Cod sursa (job #1212702) | Cod sursa (job #1875577) | Cod sursa (job #2778228) | Cod sursa (job #2486999) | Cod sursa (job #322649)
Cod sursa(job #322649)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct{
int cul;
int *vec;
int m;
}Nod;
typedef struct{
int s, d;
}Arc;
#define ALB 0
#define GRI 1
#define NEGRU 2
int main(int argc, char *argv[])
{
//deschidere fisiere
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
//declarare date, initializare, citire si alocare de memorie
Nod *v;
Arc *a;
int n, m, i, j, k, l, vf, vf1;
scanf("%d%d", &n, &m);
n++;
v = (Nod*)malloc( sizeof(*v) * n );
a = (Arc*)malloc( sizeof(*a) * m );
int *laf, *la;
laf = la = (int*)malloc( sizeof(int) * m );
int *S = (int*)malloc( sizeof(int) * n );
int *S1 = (int*)malloc( sizeof(int) * n );
for( i = 0; i < n; i++){
v[i].cul = ALB;
v[i].m = 0;
}
for( i = 0; i < m; i++){
scanf("%d%d", &a[i].s, &a[i].d);
v[a[i].s].m++;
}
//crearea listelor de adiacenta
for( i = 0; i < n; i++){
v[i].vec = la;
la += v[i].m;
v[i].m = 0;
}
for( i = 0; i < m; i++){
for( j = 0; j < v[a[i].s].m; j++)
if(v[a[i].s].vec[j] == a[i].d)
continue;
v[a[i].s].vec[v[a[i].s].m++] = a[i].d;
}
vf = 0;
for( l = 1; l < n; l++){
if(v[l].cul == ALB){
//Parcurgere DFS
S1[vf1 = 0] = l;
while(vf1 >= 0){
i = S1[vf1--];
v[i].cul = GRI;
for( j = v[i].m ; j--; ){
k = v[i].vec[j];
if(v[k].cul == ALB)
S1[++vf1] = k;
}
v[i].cul = NEGRU;
S[vf++] = i;
}
}
}
for( i = 0; i < vf; i++)
printf("%d ", S[i]);
//eliberare memorie
free( a );
free( v );
free( S );
free( S1 );
free( laf );
return 0;
}