Cod sursa(job #2016303)

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

FILE *f;
char buf[100000] = {}, *buf_p = buf, *buf_ep = buf + sizeof(buf);

void init_buf(){
    f = fopen("sortaret.in", "r"),
    fread(buf_p = buf, sizeof(char), sizeof(buf), f); }

void adv(){
    if(++buf_p == buf_ep)
        fread(buf_p = buf, sizeof(char), sizeof(buf), f); }

int get_int(){
    int x = 0;
    for( ; *buf_p < '0'; adv());
    for( ; *buf_p > '0'; adv()) x = 10 * x + *buf_p - '0';
    return x; }

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 *g = fopen("sortaret.out", "w");
    init_buf();

    int n = get_int(), m = get_int();

    for(int i = 0; i < n; ++i)
        vec[i] = build_vector();
    for(int i = 0, x, y; i < m; ++i){
        x = get_int()-1, y = get_int()-1;
        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; }