Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Diferente pentru utilizator/raluca1234 intre reviziile 14 si 13 | Profil cyrus | Cod sursa (job #2016302)
#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; }