Pagini recente » Cod sursa (job #271818) | Cod sursa (job #1275145) | Cod sursa (job #1599086) | Cod sursa (job #2813768) | Cod sursa (job #2016301)
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
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 *f = fopen("sortaret.in", "r"),
*g = fopen("sortaret.out", "w");
int n, m;
fscanf(f, "%d %d", &n, &m);
for(int i = 0; i < n; ++i)
vec[i] = build_vector();
for(int i = 0, x, y; i < m; ++i){
fscanf(f, "%d %d", &x, &y);
--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)
fprintf(g, "%d ", *p + 1);
return 0; }