/* file name: top_sort.c */
/*拓撲排序*/

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

#define MAX_V 100  /*最大節點數*/
#define TRUE 1
#define FALSE 0

/*定義數據結構*/
typedef struct node_tag {
	int vertex;
	struct node_tag *link;
} Node;

Node *adjlist[MAX_V+1];  /*宣告鄰接表*/
int visited[MAX_V+1];  /*記錄頂點是否已訪問*/
int Top_order[MAX_V+1];
int N;
int place;


void build_adjlist();
void show_adjlist();
void topological();
void top_sort(int);
Node *searchlast(Node *);

void main()
{
	int i;

	build_adjlist(); /*以鄰接表表示圖*/
	show_adjlist();   /*顯示表之數據*/
	topological();      /*圖之蹤向優先搜索，以頂點1為啟始頂點*/
	puts("\n------Toplogical order sort------");
	for ( i = 0; i < N; i++ )
		printf("V%d ",Top_order[i]);
}

void build_adjlist()
{
	FILE *fptr;
	Node *node,*lastnode;
	int vi,vj;

	fptr = fopen("top_sort.dat","r");
	if ( fptr == NULL )
	{
		perror("top_sort.dat");
		exit(0);
	}

	/*讀取節點總數*/
	fscanf(fptr,"%d",&N);
	for ( vi = 1; vi <= N; vi++)
	{
		/*設定數組及各表啟始值*/
		adjlist[vi] = (Node *)malloc(sizeof(Node));
		adjlist[vi]->vertex = vi;
		adjlist[vi]->link = NULL;
	}

	/*讀取節點數據*/
	while( fscanf(fptr,"%d %d",&vi,&vj) != EOF)
	{
		node = (Node *)malloc(sizeof(Node));
		node->vertex = vj;
		node->link = NULL;
		if ( adjlist[vi]->link == NULL)
			adjlist[vi]->link = node;
		else
		{
			lastnode = searchlast(adjlist[vi]);
			lastnode->link = node;
		}
	}
	fclose(fptr);
}

/*顯示各鄰接表之數據*/
void show_adjlist()
{
	int v;
	Node *ptr;

	puts("Head    adjacency nodes");
	puts("------------------------------");
	for (v = 1; v <= N; v++)
	{
		printf("V%d ",adjlist[v]->vertex);
		ptr = adjlist[v]->link;
		while ( ptr != NULL )
		{
			printf("--> V%d ",ptr->vertex);
			ptr = ptr->link;
		}
		printf("\n");
	}
}

/*圖之蹤向優先搜索*/
void topological()
{
	int v;

	for ( v = 1;v <= N; v++)
		visited[v] = FALSE;
	place = N;
	for ( v = 1; v <= N; v++ )
		if ( !visited[v] )
			top_sort(v);
}

void top_sort(int k)
{
	Node *ptr;
	int w;

	visited[k] = TRUE;           /*設定v頂點為已訪問過*/
	ptr = adjlist[k]->link;     /*訪問v鄰接頂點*/
	while ( ptr != NULL )
	{
		w = ptr->vertex; /* w 為v的直接后繼 */ 
		if ( !visited[w] )
			top_sort(w);
		ptr = ptr->link;
	}
	Top_order[--place] = k;
}

/*搜索表最后節點函數*/
Node *searchlast( Node *linklist )
{
	Node *ptr;

	ptr = linklist;
	while ( ptr->link != NULL ) ptr = ptr->link;
	return ptr;
}