/*   拓撲排序的實現，解決一類需要先做什么，再做什么，比如學習一系列基本教程以及施工隊進入工地的時間安排順序！

*/
#include<stdlib.h>
#include<stdio.h>
#define SIZE 100
#define MAXqueue  20      //隊列的最大容量
struct node               //圖的頂點結構聲明
{
	int vertex;                  //頂點數據
	struct node *nextnode;       //指向下一個頂點的指針
};
typedef struct node *graph;      //圖的結構新類型
struct node head[SIZE];          //圖頂點結構數組
int yjj_queue[MAXqueue];             //隊列的數組聲明
int yjj_front = -1;					 //隊列的隊頭
int yjj_rear = -1;					 //隊列的對尾
int **yjj_node;                      //保存用戶輸入的數據的一個數組（起點。終點。權值）
int yjj_cost[SIZE][SIZE];            //保存權值，yjj_cost[0][0]里面的沒有


/* ----------------------------------*/
/*    create the graph contion du    */
/* ----------------------------------*/


void creategraph(graph head,int **node,int num)
{
	graph newnode;           //新頂點指針
	graph ptr;
	int from;                //邊的起點
	int to;                  //邊的終點
	int i;

	for(i = 0;i < num;i++)                               //讀取邊的循環
	{
		from = node[i][0];                               //邊的起點
		to = node[i][1];                                 //邊的終點
	   	yjj_cost[from][to] = node[i][2];
		head[to].vertex += 1;                            //入度加一
		/* create newnode */
		newnode = (graph )malloc(sizeof(struct node));
		newnode->vertex = to;
		newnode->nextnode = NULL;
		ptr = &(head[from]);
		while(ptr->nextnode != NULL)
			ptr = ptr->nextnode;                          //下一個頂點
		ptr->nextnode = newnode;                          //插入結尾
	}
}


/* ----------------------------------*/
/*        excute the toposort        */
/* ----------------------------------*/
int toposort(graph head,int num)
{
	graph ptr;
	int i;

	/* 將入度為零的頂點存入隊列的循環*/
	for( i = 1;i <= num*2;i++)
	{
		ptr = head[i].nextnode;                               
		if(head[i].vertex == 0&&ptr ->nextnode != NULL)   //入度為零
	 		enqueue(i);           //存頂點到隊列
		ptr = NULL;
	}
	while((i = dequeue())!= -1)
	{
		printf("%d ",i);            //輸出拓撲排序的頂點
		ptr = head[i].nextnode;     //頂點位置
		while(ptr != NULL)
		{
			i = ptr -> vertex;                //得到頂點值
			head[i].vertex --;                //頂點入度減一
			if(head[i].vertex == 0)           //如果入度是0
				enqueue(i);                   //存頂點到隊列
	 		ptr = ptr -> nextnode;            //下一個頂點

		}
	}
	printf("\n");
	for( i = 1;i <= num;i++)                 //  檢查是否有循環  
	if(head[i].vertex != 0)                  //  入度不是0
		return 1;                            //  有回路
	return 0;                                //  沒有回路
}


/* --------------------------*/
/*        duilie data save   */
/* --------------------------*/

int enqueue(int value)                  //向隊列里插入數據
{
	if(yjj_rear + 1 == yjj_front || yjj_rear == (MAXqueue - 1)&&yjj_front <= 0)       // 檢查隊列是否已滿
		return -1;                                                    // 無法存入
	yjj_rear ++;                                                          //隊尾指針往前移動
	if(yjj_rear == MAXqueue)                                              //是否超過界限
		yjj_rear =  0 ;                                                      //從頭開始
	yjj_queue[yjj_rear] = value;                                              //存入隊列
}

/* --------------------------*/
/*        duilie data output   */
/* --------------------------*/

int dequeue()                           //取出數據
{
	if(yjj_front == yjj_rear)                                                //檢查隊列是否為空
	{
		return -1;                                                   //無法取出
	}
	yjj_front ++;                                                        //隊頭指針往前移動
	if(yjj_front == MAXqueue)                                            //是否超過界限
		yjj_front = 0;                                                   //從頭開始
	return yjj_queue[yjj_front];                                             //隊列取出
}

/* --------------------------*/
/*      the main fuction     */
/* --------------------------*/
void main()
{
	graph  ptr;
    /*----------------------------------------------------------------*/
	int m,n=3;            //控制動態二維數據的聲請
    int i;
	clrscr();
	/* 建立二維數組保存用戶的輸入：包括（起點，終點，以及權值）*/
	printf("Please input one number:\n");
	scanf("%d",&m);
	yjj_node = (int **) malloc(m*sizeof(int *));
	for(i = 0;i < m;i ++)
		yjj_node[i] = (int *)malloc(n*sizeof(int));
	for(i = 0;i < m;i ++)
		{
			printf("Please input datas:\n");
			scanf ("%d,%d,%d",&yjj_node[i][0],&yjj_node[i][1], &yjj_node[i][2]) ;
		}
    /*----------------------------------------------------------------*/

	for(i =1;i <=SIZE;i++)
	{
		head[i].vertex = 0;                           //設置頂點值
		head[i].nextnode = NULL;                      //清除圖的指針
	}
	creategraph( head,yjj_node,m);
    //creategraph( head2,node,10);
	printf("fisrt graph:\n");
	if(toposort( head, m))                            //拓撲排序
		printf("have ciycal:\n");
	else 
		printf("do not have ciycal:\n");
	yjj_front = yjj_rear = -1;                                 //清除隊列
}