Cod sursa(job #936651)

Utilizator shiftcrissCeica Cristian shiftcriss Data 8 aprilie 2013 02:16:20
Problema Sortare topologica Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#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;
}