Cod sursa(job #2016301)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 29 august 2017 04:39:19
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.34 kb
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct vector{
    int sz, capacity, *buf; } vector;

vector build_vector(){
    vector rez;
    rez.sz = 0;
    rez.capacity = 1;
    rez.buf = malloc(1 * sizeof(int));
    return rez; }

void push_back(vector* v, int x){
    if(v->sz == v->capacity){
        int *tmp = malloc(2 * v->capacity * sizeof(int));
        memcpy(tmp, v->buf, v->capacity * sizeof(int));

        v->buf = tmp;
        v->capacity *= 2; }
    v->buf[v->sz++] = x; }

#define MAXN (50000+10)

vector vec[MAXN];
int nr_prevs[MAXN] = {}, st[MAXN], *st_p = st, rez[MAXN], *rez_p = rez;

int main(){
    FILE *f = fopen("sortaret.in", "r"),
        *g = fopen("sortaret.out", "w");
    int n, m;
    fscanf(f, "%d %d", &n, &m);

    for(int i = 0; i < n; ++i)
        vec[i] = build_vector();
    for(int i = 0, x, y; i < m; ++i){
        fscanf(f, "%d %d", &x, &y);
        --x, --y;
        push_back(vec + x, y);
        ++nr_prevs[y]; }
    for(int i = 0; i < n; ++i)
        if(nr_prevs[i] == 0)
            *st_p++ = i;
    while(st_p != st){
        int cur = *--st_p;
        *rez_p++ = cur;
        for(int i = 0; i < vec[cur].sz; ++i)
            if(--nr_prevs[vec[cur].buf[i]] == 0)
                *st_p++ = vec[cur].buf[i]; }
    for(int *p = rez; p < rez_p; ++p)
        fprintf(g, "%d ", *p + 1);
    return 0; }