#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
typedef int Status; /* 函数结果状态代码,如OK等 */
#define INFINITY INT_MAX /* 用整型最大值代替∞ */
#define MAX_VERTEX_NUM 50 /* 最大顶点个数 */
typedef int VRType;
typedef char InfoType;
typedef int VertexType;
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct {
	VRType adj; /* 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； */
	/* 对带权图，c则为权值类型 */
	InfoType *info; /* 该弧相关信息的指针(可无) */
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
	VertexType vexs[MAX_VERTEX_NUM]; /* 顶点向量 */
	AdjMatrix arcs; /* 邻接矩阵 */
	int vexnum,arcnum; /* 图的当前顶点数和弧数 */
	GraphKind kind; /* 图的种类标志 */
}MGraph;

Status CreateUDG(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,由文件构造没有相关信息的无向图G */
	int i,j;
	scanf("%d",&(*G).vexnum);
	for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
		(*G).vexs[i] = i;
	for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
		for(j=0;j<(*G).vexnum;++j)
		{
			scanf("%d",&(*G).arcs[i][j].adj); /* 图 */
			(*G).arcs[i][j].info=NULL; /* 没有相关信息 */
		}
	(*G).kind=AG;
	return OK;
}

int LocateVex(MGraph G,VertexType u)
{ /* 初始条件:图G存在,u和G中顶点有相同特征 */
	/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
	int i;
	for(i=0;i<G.vexnum;++i)
		if(u == G.vexs[i])
			return i;
	return -1;
}

VertexType* GetVex(MGraph G,int v)
{ /* 初始条件: 图G存在，v是G中某个顶点的序号。操作结果: 返回v的值 */
	if(v>=G.vexnum||v<0)
		exit(ERROR);
	return &G.vexs[v];
}

int FirstAdjVex(MGraph G,VertexType v)
{ /* 初始条件: 图G存在,v是G中某个顶点 */
	/* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */
	int i,j=0,k;
	k=LocateVex(G,v); /* k为顶点v在图G中的序号 */
	if(G.kind==DN||G.kind==AN) /* 网 */
	j=INFINITY;
	for(i=0;i<G.vexnum;i++)
	if(G.arcs[k][i].adj!=j)
	return i;
	return -1;
}

int NextAdjVex(MGraph G,VertexType v,VertexType w)
{ /* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 */
	/* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号, */
	/*           若w是v的最后一个邻接顶点,则返回-1 */
	int i,j=0,k1,k2;
	k1=LocateVex(G,v); /* k1为顶点v在图G中的序号 */
	k2=LocateVex(G,w); /* k2为顶点w在图G中的序号 */
	if(G.kind==DN||G.kind==AN) /* 网 */
	j=INFINITY;
	for(i=k2+1;i<G.vexnum;i++)
	if(G.arcs[k1][i].adj!=j)
	return i;
	return -1;
}

bool visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
Status(*VisitFunc)(VertexType); /* 函数变量 */
void DFS(MGraph G,int v)
{ /* 从第v个顶点出发递归地深度优先遍历图G。算法7.5 */
	VertexType w1,v1;
	int w;
	visited[v]=TRUE; /* 设置访问标志为TRUE(已访问) */
	VisitFunc(G.vexs[v]); /* 访问第v个顶点 */
	v1 = *GetVex(G,v);
	for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,w1 = *GetVex(G,w)))
	if(!visited[w]) DFS(G,w); /* 对v的尚未访问的序号为w的邻接顶点递归调用DFS */
}

void DFSTraverse(MGraph G,Status(*Visit)(VertexType))
{ /* 初始条件: 图G存在,Visit是顶点的应用函数。算法7.4 */
	/* 操作结果: 从第1个顶点起,深度优先遍历图G,并对每个顶点调用函数Visit */
	/*           一次且仅一次。一旦Visit()失败,则操作失败 */
	int v;
	VisitFunc=Visit; /* 使用全局变量VisitFunc,使DFS不必设函数指针参数 */
	for(v=0;v<G.vexnum;v++)
		visited[v]=FALSE; /* 访问标志数组初始化(未被访问) */
	for(v=0;v<G.vexnum;v++)
		if(!visited[v])
			DFS(G,v); /* 对尚未访问的顶点调用DFS */
	printf("\n");
}

Status visit(VertexType i)
{
	printf("%d ",i);
	return OK;
}

int main() {
	int i,j,k,n;
	MGraph g;
	CreateUDG(&g);
	DFSTraverse(g,visit);
	return 0;
}

/**************************************************************
	Problem: 2159
	User: admin
	Language: C++
	Result: Runtime Error
****************************************************************/