Pagini recente » Cod sursa (job #2885019) | Cod sursa (job #782964) | Profil StarGold2 | Cod sursa (job #122340) | Cod sursa (job #2016308)
#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; }