linklist

linklist.c

#include <stdio.h>
#include <stdlib.h>

static int input[] = {
	9, 2,
	3, 7,
	7, 5,
	5, 8,
	8, 6,
	4, 6,
	1, 3,
	7, 4,
	9, 5,
	2, 8,
};

struct top {
	struct top *next;
	int suc;
};


struct entry {
	union {
		int count;
		int next;
	} u;
	struct top *top;
};

int main()
{
	int i;
	int N = 9 + 1;
	int IN = sizeof(input) / sizeof(input[0]) / 2;
	void *p = malloc(N * sizeof(struct entry) + sizeof(struct top) * IN);
	struct entry *entrybase = (struct entry *)p;
	struct top *topbuff = (struct top *)(entrybase + N);
	struct entry *q;
	//init
	for (i = 0; i < N; i++) {
		entrybase[i].top = NULL;
		entrybase[i].u.count = 0;
	}
	//input
	for (i = 0; i < IN * 2; i++) {
		int a = input[i++];
		int b = input[i];
		struct entry *e = entrybase + a;
		struct top *t = topbuff++;
		t->next = e->top;
		e->top = t;
		t->suc = b;
		entrybase[b].u.count++;
	}
	q = entrybase;
	//first
	for (i = 1; i < N; i++) {
		if (entrybase[i].u.count)
			continue;
		q->u.next = i;
		q = &entrybase[i];
	}
	//propagate
	for (i = entrybase[0].u.next; i; ) {
		struct entry *e = &entrybase[i];
		struct top *t = e->top;
		while (t) {
			int suc = t->suc;
			if ((--entrybase[suc].u.count) == 0) {
				q->u.next = suc;
				q = &entrybase[suc];
			}
			t = t->next;
		}
		i = e->u.next;
	}

	for (i = entrybase[0].u.next; i; ) {
		printf("%d ", i);
		i = entrybase[i].u.next;
	}
	printf("\n");