PTA练习题6-1 Is Topological Order (25 分)

这道题是输入一个有向图，然后输入几组序列 ，判断是否是是否是拓扑序列。题目如下：
Write a program to test if a give sequence Seq is a topological order of a given graph Graph.
Format of functions:
bool IsTopSeq( LGraph Graph, Vertex Seq[] );
where LGraph is defined as the following:
图的定义如下：

typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{
    Vertex AdjV;
    PtrToAdjVNode Next;
};

typedef struct Vnode{
    PtrToAdjVNode FirstEdge;
} AdjList[MaxVertexNum];

typedef struct GNode *PtrToGNode;
struct GNode{  
    int Nv;
    int Ne;
    AdjList G;
};
typedef PtrToGNode LGraph;

The function IsTopSeq must return true if Seq does correspond to a topological order; otherwise return false.
Note: Although the vertices are numbered from 1 to MaxVertexNum, they are indexed from 0 in the LGraph structure.

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

typedef enum {false, true} bool;
#define MaxVertexNum 10  /* maximum number of vertices */
typedef int Vertex;      /* vertices are numbered from 1 to MaxVertexNum */

typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{
    Vertex AdjV;
    PtrToAdjVNode Next;
};

typedef struct Vnode{
    PtrToAdjVNode FirstEdge;
} AdjList[MaxVertexNum];

typedef struct GNode *PtrToGNode;
struct GNode{  
    int Nv;
    int Ne;
    AdjList G;
};
typedef PtrToGNode LGraph;

LGraph ReadG(); /* details omitted */

bool IsTopSeq( LGraph Graph, Vertex Seq[] );

int main()
{
    int i, j, N;
    Vertex Seq[MaxVertexNum];
    LGraph G = ReadG();
    scanf("%d", &N);
    for (i=0; i<N; i++) {
        for (j=0; j<G->Nv; j++)
            scanf("%d", &Seq[j]);
        if ( IsTopSeq(G, Seq)==true ) printf("yes\n");
        else printf("no\n");
    }

    return 0;
}

/* Your function will be put here */

下边是样例输入和输出：

Sample Input (for the graph shown in the figure):
6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
5
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6

Sample Output:
yes
yes
yes
no
no

首先这个题需要注意很多点，因为我做的时候没想到这些，导致我很长时间才做出来，其实这道题思路并不难。
先说注意的点吧（讲道理，全英文的题真的有点xx，对我这种英文不好的人真是煎熬）：

1. 题目中的MaxVertexNUm在测试过程中是会改变的，我一开始以为就固定是题目中的10了，所以最后一个测试点始终是段错误。具体我也不知道最后一个测试点是多大，反正我给搞了个1000。
2. 题目中提示了，虽然数据都是从1开始的，但是代码中的下标都是从0开始的。解释一下，就是比如输入样例中的第二行”1 2“这个数据，要表示节点1后边连着节点2，但是储存在数组中就是G[0]的后边连着节点2。
3. 思路的话，我看别人都是遍历图然后求各个节点的入度，最后在与输入的数据一个个对比。我的思路跟他们不太一样，我创建了一个大小1000数组，存有0和1，0代表节点没有输出过，1反之。然后遍历邻接链表，查询每个节点的邻接节点，判断是否
   含有Seq[i]，如果含有证明Seq[i]入度不为零，则不是拓扑序列。

我表达能力确实有限，可能我自己再回头看都看不懂我的话，直接上代码简单些。我大概猜到题目中省略的ReadG()函数，如下：

LGraph ReadG()
{
    int i;
    LGraph LG = (LGraph)malloc(sizeof(GNode));
	for(int j=0;j<10;j++)
		LG->G[j].FirstEdge=NULL;
    scanf("%d %d", &LG->Nv, &LG->Ne);
    for(i = 0; i < LG->Ne; ++i)
    {
        int p1, p2;
        PtrToAdjVNode adj = (AdjVNode *)malloc(sizeof(AdjVNode));
        scanf("%d %d", &p1, &p2);
		p1--;p2--;  //注意这里，他输入后都减了1！！！
        adj->AdjV = p2;
        adj->Next = NULL;
        if(LG->G[p1].FirstEdge == NULL)
        {
            LG->G[p1].FirstEdge = adj;
        }
        else
        {
            adj->Next = LG->G[p1].FirstEdge;
            LG->G[p1].FirstEdge = adj;
        }
    }
    return LG;
}

然后就是我自己写的要提交的代码：

bool IsTopSeq( LGraph Graph, Vertex Seq[] ) {
	int a[1000];//用来储存节点是否输出过的数组
	for(int i=0; i<1000; i++)
		a[i]=0;//初始化为0.表明节点都没输出过
	PtrToAdjVNode p;
	for(int i=0; i<Graph->Nv; i++)//遍历输入的序列
     {
		 Seq[i]--;//关键点！！！！根据上边的分析，将要判断的数组每个数都减1
		for(int j=0; j<Graph->Nv; j++) //遍历图的邻接链表
        {
			if(a[j]==1||j==Seq[i])//如果当前节点输出过，或者和要判断的序列节点相同，跳过，我个人认为可能节省点时间吧。嘿嘿
				continue;
			else 
            {
				p=Graph->G[j].FirstEdge;
				while(p) 
                {
					if(p->AdjV==Seq[i])
						return false;
					p=p->Next;
				}
			}
		}
		a[Seq[i]]=1;
	}
	return true;
}

讲道理，我最喜欢看这种图片，自己加油，每个程序员加油！！！