Pagini recente » Istoria paginii runda/ziua_recursivitatii | Cod sursa (job #1822693) | Cod sursa (job #1197802) | Istoria paginii runda/corona_day1/clasament | Cod sursa (job #1486041)
#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;
}