Cod sursa(job #2016308)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 29 august 2017 05:09:48
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 2.29 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 init_i_buf(){
    f = fopen("sortaret.in", "r"),
    fread(i_buf_p = i_buf, sizeof(char), sizeof(i_buf), f); }
 
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 init_o_buf(){
    g = fopen("sortaret.out", "w"); }
 
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; }
 
static void print_char(char ch){
    *o_buf_p++ = ch; }
     
static void close_o_buf(){
    fwrite(o_buf, o_buf_p - o_buf, sizeof(char), g); }
 
typedef struct vector{
    int sz, capacity, *buf; } vector;
 
static vector build_vector(){
    vector rez;
    rez.sz = 0;
    rez.capacity = 4;
    rez.buf = malloc(4 * sizeof(int));
    return rez; }
 
static 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 *= 3;
        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(){
    init_i_buf();
    init_o_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();
        y = get_int();
        --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){
        print_int(*p + 1);
        print_char(' '); }
 
    close_o_buf();
    return 0; }