Cod sursa(job #2016307)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 29 august 2017 05:06:20
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.69 kb
#pragma GCC optimize ("O3")
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

FILE *f;
char i_buf[100000] = {}, *i_buf_p = i_buf, *i_buf_ep = i_buf + sizeof(i_buf);

static void adv(){
    if(++i_buf_p == i_buf_ep)
        fread(i_buf_p = i_buf, sizeof(char), sizeof(i_buf), f); }

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

FILE *g;
char o_buf[300000] = {}, *o_buf_p = o_buf;

static void print_int(int x){
    static char buf[10], *p = buf;
    for( ; x; x /= 10) *p++ = x % 10 + '0';
    while(p > buf) *o_buf_p++ = *--p; }

typedef struct nod{
    int val; struct nod *next; } nod;

nod *mk_nod(int x, nod *n){
    nod *r = malloc(sizeof(nod));
    r->val = x, r->next = n;
    return r; }

#define MAXN (50000+10)

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

int main(){
    f = fopen("sortaret.in", "r"),
    g = fopen("sortaret.out", "w");
    fread(i_buf_p = i_buf, sizeof(char), sizeof(i_buf), f);

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

    for(int i = 0, x, y; i < m; ++i){
        x = get_int();
        y = get_int();
        --x, --y;
        vec[x] = mk_nod(y, vec[x]);
        ++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(nod *n = vec[cur]; n; n = n->next)
            if(--nr_prevs[n->val] == 0)
                *st_p++ = n->val; }
    for(int *p = rez; p < rez_p; ++p){
        print_int(*p + 1);
        *o_buf_p++ = ' '; }

    fwrite(o_buf, o_buf_p - o_buf, sizeof(char), g);
    return 0; }