Pagini recente » Cod sursa (job #313629) | Monitorul de evaluare | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #2016307)
#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; }