Cod sursa(job #1486041)

Utilizator mike93Indricean Mihai mike93 Data 13 septembrie 2015 18:22:42
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.73 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct vectorInt {
	int* data;
	int size;
	int capacity;
} vectInt;
typedef vectInt* vector;

vector vec_new(int initCap) {
	if(initCap < 10) {
		initCap = 10;
	}
	vector vect = (vector)malloc(sizeof(vectInt));
	vect->capacity = initCap;
	vect->size = 0;
	vect->data = (int*)malloc(vect->capacity * sizeof(int));
	return vect;
}

void vec_free(vector vect) {
	free(vect->data);
	free(vect);
}

void vec_push_back(vector vect, int val) {
	if(vect->size == vect->capacity) {
		vect->capacity = 2 * vect->capacity;
		int* newData = (int*)malloc(vect->capacity * sizeof(int));
		memcpy(newData, vect->data, vect->size * sizeof(int));
		free(vect->data);
		vect->data = newData;
	}
	vect->data[vect->size] = val;
	vect->size++;
}

int main() {
	FILE* fin = fopen("sortaret.in", "r");
	int n, m;
	fscanf(fin, "%d %d\n", &n, &m);
	vector* g = (vector*)malloc((n + 1) * sizeof(vector));
	int* deg = (int*)malloc((n + 1) * sizeof(int));
	int i;
	for(i=0; i<=n; i++) {
		deg[i] = 0;
		g[i] = vec_new(0);
	}
	int x, y;
	for(i=0; i<m; i++) {
		fscanf(fin, "%d %d\n", &x, &y);
		vec_push_back(g[y], x);
		deg[x]++;
	}
	fclose(fin);
	
	vector q = vec_new(n);
	for(i=1; i<=n; i++) {
		if(deg[i] == 0) {
			vec_push_back(q, i);
		}
	}
	
	int j;
	for(i=0; i<n; i++) {
		x = q->data[i];
		for(j=0; j<g[x]->size; j++) {
			deg[g[x]->data[j]]--;
			if(deg[g[x]->data[j]] == 0) {
				vec_push_back(q, g[x]->data[j]);
			}
		}
	}
	
	FILE* fout = fopen("sortaret.out", "w");
	for(i=n-1; i>=0; i--) {
		fprintf(fout, "%d ", q->data[i]);
	}
	fclose(fout);
	vec_free(q);
	free(deg);
	for(i=0; i<=n; i++) {
		vec_free(g[i]);
	}
	return 0;
}