Cod sursa(job #936652)

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