Pagini recente » Cod sursa (job #1433257) | Cod sursa (job #2556614) | Cod sursa (job #1075503) | Cod sursa (job #1657912) | Cod sursa (job #936652)
Cod sursa(job #936652)
#include<stdio.h>
#include<stdlib.h>
#include <queue>
using namespace std;
long **adj_matrix,i,j,num_nodes,*grad_long,nr,m;
queue<long> coada;
long cauta()
{for(long i = 0; i <= num_nodes; i++)
if(grad_long[i] == 0)
return i;
return -1;
}
int main()
{
FILE *in,*out;
in = fopen("sortaret.in","r");
out = fopen("sortaret.out","w");
fscanf(in,"%ld %ld",&num_nodes,&m);
for(i = 0; i < num_nodes; i++)
grad_long = (long*)malloc(num_nodes*sizeof(long));
for(i = 0; i < num_nodes; i++)
grad_long[i] = 0;
adj_matrix = (long**)malloc(num_nodes*sizeof(long*));
for(i = 0; i < num_nodes; i++)
adj_matrix[i] = (long*)malloc(num_nodes*sizeof(long));
for(i = 0; i < num_nodes; i++)
for(j = 0; j < num_nodes ; j++) {
adj_matrix[i][j] = 0;
}
long a,b;
for(i = 0; i < m; i++) {
fscanf(in,"%ld %ld ",&a,&b);
adj_matrix[a-1][b-1] = 1;
}
for(i = 0; i < num_nodes; i++){
nr = 0;
for(j = 0; j < num_nodes ; j++) {
if(adj_matrix[j][i] == 1) nr++;
}
grad_long[i] = nr;
}
for(i = 0; i < num_nodes; i++)
if(grad_long[i] == 0)
coada.push(i);
while(!coada.empty()) {
long x = coada.front();
fprintf(out,"%d ",x+1);
coada.pop();
for(i = 0; i < num_nodes; i++)
if(adj_matrix[x][i] == 1 && grad_long[i] != 0) {
grad_long[i]--;
adj_matrix[x][i] = 0;
if(grad_long[i] == 0)
coada.push(i);
}
}
return 0;
}