Pagini recente » Cod sursa (job #2546058) | Cod sursa (job #2228682) | Cod sursa (job #662530) | Cod sursa (job #1644084) | Cod sursa (job #936651)
Cod sursa(job #936651)
#include<stdio.h>
#include<stdlib.h>
#include <queue>
using namespace std;
int **adj_matrix,i,j,num_nodes,*grad_int,nr,*nod_parc,m;
queue<int> coada;
int cauta()
{for(int i = 0; i <= num_nodes; i++)
if(grad_int[i] == 0)
return i;
return -1;
}
void parc()
{ int j = 0;
while(!coada.empty()) {
nod_parc[j++] = coada.front();
coada.pop();
for(i = 0; i < num_nodes; i++)
if(adj_matrix[nod_parc[j-1]][i] == 1 && grad_int[i] != 0) {
grad_int[i]--;
adj_matrix[nod_parc[j-1]][i] = 0;
if(grad_int[i] == 0)
coada.push(i);
}
}
}
int main()
{
FILE *in,*out;
in = fopen("sortaret.in","r");
out = fopen("sortaret.out","w");
fscanf(in,"%d %d",&num_nodes,&m);
for(i = 0; i < num_nodes; i++)
grad_int = (int*)malloc(num_nodes*sizeof(int));
for(i = 0; i < num_nodes; i++)
grad_int[i] = 0;
adj_matrix = (int**)malloc(num_nodes*sizeof(int*));
for(i = 0; i < num_nodes; i++)
adj_matrix[i] = (int*)malloc(num_nodes*sizeof(int));
for(i = 0; i < num_nodes; i++)
for(j = 0; j < num_nodes ; j++) {
adj_matrix[i][j] = 0;
}
nod_parc = (int*) malloc(num_nodes*sizeof(int));
for(i = 0; i <= num_nodes; i++)
nod_parc[i] = 0;
int a,b;
for(i = 0; i < m; i++) {
fscanf(in,"%d %d ",&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_int[i] = nr;
}
for(i = 0; i < num_nodes; i++)
if(grad_int[i] == 0)
coada.push(i);
parc();
for(i = 0; i < num_nodes; i++)
fprintf(out,"%d ",nod_parc[i]+1);
return 0;
}