Алгоритмы на графах

Artem Voroztsov - 13 Apr 2005

#include <stdio.h>

#define N 1000

typedef struct item {
  struct item *next;
  int id;
  item(struct item *n, int a): next(n), id(a) {};
} item;

int stack[N];
item *e[N];
int sp=0;
int n;

void
push(int a)
{
  stack[sp++] = a;
}

int
pop()
{
  if(sp>0)
  {
    printf("%d ", stack[sp-1] + 1);
    return stack[--sp];
  } else {
     printf("Stack is empty\n");
     return -1;
  }
}

int last()
{
  return stack[sp-1];
}

int walk()
{
    int a = last();
    if( e[a] != NULL)
    {
      item *next = e[a];
      push (next->id);
      next = next->next;
      delete ( e[a] );
      e[a] = next;
      walk();
    }
    return pop();
}

int main()
{
  char buf[1000];
  int shift = 0, j=0, i, a, k;
  scanf("%d", &n);

  memset(e, 0, sizeof(item)*n);
  scanf("\n");
  for(i=0; i < n; i++)
  {
      fgets(buf,1000, stdin);
      shift = j = 0;
      while(sscanf(buf+shift,"%d%n", &a, &k ) == 1)
      {
        shift += k;
        e[i] = new item(e[i], a-1);
        j++;
      }
  }
  
  push(1);
  walk();
  return 0;
}