unsigned int	o;  o = 1;
static struct node *find_good_cycle_break __P((struct array *));static void print_cycle __P((struct array *));static int find_cycle_with __P((struct node *, struct array *));static struct node *find_predecessor __P((struct array *, struct node *));static unsigned int traverse_node __P((struct node *, unsigned int, struct array *));static struct node *find_longest_cycle __P((struct array *, struct array *));static void heap_down __P((struct array *, unsigned int));static void heapify __P((struct array *, int));static struct node *dequeue __P((struct array *));static void enqueue __P((struct array *, struct node *));#define erealloc(n, s)	emem(realloc(n, s))static void *hash_alloc __P((size_t, void *));static void hash_free __P((void *, size_t, void *));static void* entry_alloc __P((size_t, void *));static void *emalloc __P((size_t));static void *emem __P((void *));#define DEBUG_TRAVERSE 0static struct ohash_info node_info = { 	offsetof(struct node, k), NULL, hash_alloc, hash_free, entry_alloc };int main __P((int, char *[]));/*** *** Memory handling.  ***/static void *emem(p)	void 		*p;{	if (p)		return p;	else		errx(EX_SOFTWARE, "Memory exhausted");}static void *hash_alloc(s, u)	size_t s;	void *u		UNUSED;{	return emem(calloc(s, 1));}static voidhash_free(p, s, u)	void *p;	size_t s	UNUSED;	void *u		UNUSED;{	free(p);}static void *entry_alloc(s, u)	size_t s;	void *u		UNUSED;{	return emalloc(s);}static void *emalloc(s)	size_t s;{	return emem(malloc(s));}/***  *** Hash table. ***//* Inserting and finding nodes in the hash structure. * We handle interval strings for efficiency wrt fgetln.  */static struct node *new_node(start, end)	const char 	*start;	const char 	*end;{	struct node 	*n;	n = ohash_create_entry(&node_info, start, &end);	n->from = NULL;	n->arcs = NULL;	n->refs = 0;	n->mark = 0;	n->order = 0;	n->traverse = NULL;	return n;}static void nodes_init(h)	struct ohash 	*h;{	ohash_init(h, HASH_START, &node_info);}static struct node *node_lookup(h, start, end)	struct ohash 	*h;	const char 	*start;	const char 	*end;{	unsigned int	i;	struct node *	n;	i = ohash_qlookupi(h, start, &end);	n = ohash_find(h, i);	if (n == NULL)		n = ohash_insert(h, i, new_node(start, end));	return n;}	#ifdef DEBUGstatic voiddump_node(n)    struct node 	*n;{	struct link 	*l;	if (n->refs == 0)		return;	printf("%s (%u): ", n->k, n->refs);	for (l = n->arcs; l != NULL; l = l->next)		if (n->refs != 0)		printf("%s(%u) ", l->node->k, l->node->refs);    	putchar('\n');}static voiddump_array(a)	struct array	*a;{	unsigned int 	i;	for (i = 0; i < a->entries; i++)		dump_node(a->t[i]);}		static void dump_hash(h)	struct hash 	*h;{	unsigned int 	i;	struct node 	*n;	for (n = ohash_first(h, &i); n != NULL; n = ohash_next(h, &i))		dump_node(n);}#endif		/*** *** Reading data. ***/static void insert_arc(a, b)	struct node 	*a, *b;{	struct link 	*l;	/* Check that this arc is not already present.  */	for (l = a->arcs; l != NULL; l = l->next) {		if (l->node == b)			return;	}	b->refs++;	l = emalloc(sizeof(struct link));	l->node = b;	l->next = a->arcs;	a->arcs = l;}static voidread_pairs(f, h, reverse, name)	FILE 		*f;	struct ohash 	*h;	int 		reverse;	const char 	*name;{	int 		toggle;	struct node 	*a;	size_t 		size;	char 		*str;	unsigned int	o;	o = 1;	toggle = 1;	a = NULL;		while ((str = fgetln(f, &size)) != NULL) {		char *sentinel;		sentinel = str + size;		for (;;) {			char *e;			while (isspace(*str) && str < sentinel) 				str++;			if (str == sentinel)				break;			for (e = str; !isspace(*e) && e < sentinel; e++)				continue;			if (toggle) {				a = node_lookup(h, str, e);				if (a->order == 0)					a->order = o++;			} else {				struct node *b;				b = node_lookup(h, str, e);				assert(a != NULL);				if (b != a) {					if (reverse) 						insert_arc(b, a);					else 						insert_arc(a, b);				}			}			toggle = !toggle;			str = e;		}	}	if (toggle == 0)		errx(EX_DATAERR, "odd number of pairs in %s", name);    	if (!feof(f))		err(EX_IOERR, "error reading %s", name);}static voidread_hints(f, h, quiet, name)	FILE 		*f;	struct ohash 	*h;	int 		quiet;	const char 	*name;{	char 		*str;	size_t 		size;	unsigned int 	i;	i = 1;	while ((str = fgetln(f, &size)) != NULL) {		char *sentinel;		sentinel = str + size;		for (;;) {			char *e;			struct node *a;			while (isspace(*str) && str < sentinel) 				str++;			if (str == sentinel)				break;			for (e = str; !isspace(*e) && e < sentinel; e++)				continue;			a = node_lookup(h, str, e);			if (a->order != 0)				if (!quiet)				    warnx(					"duplicate node %s in hints file %s",					a->k, name);			else				a->order = i++;			str = e;		}	}}/*** *** Standard heap handling routines.   ***/static void heap_down(h, i)	struct array 	*h;	unsigned int 	i;{	unsigned int 	j;	struct node 	*swap;	for (; (j=2*i+1) < h->entries; i = j) {		if (j+1 < h->entries && h->t[j+1]->order < h->t[j]->order)		    	j++;		if (h->t[i]->order <= h->t[j]->order)			break;		swap = h->t[i];		h->t[i] = h->t[j];		h->t[j] = swap;	}}static void heapify(h, verbose)	struct array 	*h;	int		verbose;{	unsigned int 	i;	for (i = h->entries; i != 0;) {		if (h->t[--i]->order == 0 && verbose)			warnx("node %s absent from hints file", h->t[i]->k);		heap_down(h, i);	}}#define DEQUEUE(h) ( hints_flag ? dequeue(h) : (h)->t[--(h)->entries] )static struct node *dequeue(h)	struct array 	*h;{	struct node 	*n;	if (h->entries == 0)		n = NULL;	else {		n = h->t[0];		if (--h->entries != 0) {		    h->t[0] = h->t[h->entries];		    heap_down(h, 0);		}	}	return n;}	#define ENQUEUE(h, n) do {			\	if (hints_flag)				\		enqueue((h), (n));		\	else					\		(h)->t[(h)->entries++] = (n);	\	} while(0);static void enqueue(h, n)	struct array 	*h;	struct node 	*n;{	unsigned int 	i, j;	struct node 	*swap;	h->t[h->entries++] = n;	for (i = h->entries-1; i > 0; i = j) {		j = (i-1)/2;		if (h->t[j]->order < h->t[i]->order)			break;		swap = h->t[j];		h->t[j] = h->t[i];		h->t[i] = swap;	}}/*** *** Search through hash array for nodes. ***//* Split nodes into unrefed nodes/live nodes.  */static voidsplit_nodes(hash, heap, remaining)	struct ohash 	*hash;	struct array 	*heap;	struct array	*remaining;{	struct node *n;	unsigned int i;	heap->t = emalloc(sizeof(struct node *) * ohash_entries(hash));	remaining->t = emalloc(sizeof(struct node *) * ohash_entries(hash));	heap->entries = 0;	remaining->entries = 0;	for (n = ohash_first(hash, &i); n != NULL; n = ohash_next(hash, &i)) {		if (n->refs == 0) 			heap->t[heap->entries++] = n;		else			remaining->t[remaining->entries++] = n;	}}/* Good point to break a cycle: live node with as few refs as possible. */static struct node *find_good_cycle_break(h)	struct array 	*h;{	unsigned int 	i;	unsigned int 	best; 	struct node 	*u; 	best = UINT_MAX;	u = NULL;	assert(h->entries != 0);	for (i = 0; i < h->entries; i++) {		struct node *n = h->t[i];		/* No need to look further. */				if (n->refs == 1)			return n;		if (n->refs != 0 && n->refs < best) {			best = n->refs;			u = n;		}	}	assert(u != NULL);	return u;}