关于这道题，我要说两句，这道题我觉得我用拓扑排序的思路肯定是没错的，而且也对了几组数据，但是其他几组却超时，肯定是哪里的代码优化的不够好。。。。。。
最后只得了40分。。。
旅行商(TSP)
描述
Shrek是一个大山里的邮递员，每天负责给所在地区的n个村庄派发信件。但杯具的是，由于道路狭窄，年久失修，村庄间的道路都只能单向通过，甚至有些村庄无法从任意一个村庄到达。这样我们只能希望尽可能多的村庄可以收到投递的信件。
Shrek希望知道如何选定一个村庄A作为起点（我们将他空投到该村庄），依次经过尽可能多的村庄，路途中的每个村庄都经过仅一次，最终到达终点村庄B，完成整个送信过程。这个任务交给你来完成。
输入
第一行包括两个整数n，m，分别表示村庄的个数以及可以通行的道路的数目。
以下共m行，每行用两个整数v1和v2表示一条道路，两个整数分别为道路连接的村庄号，道路的方向为从v1至v2，n个村庄编号为[1, n]。
输出
输出一个数字，表示符合条件的最长道路经过的村庄数。
输入样例
4 3
1 4
2 4
4 3
输出样例
3
限制
1 ≤ n ≤ 1,000,000
0 ≤ m ≤ 1,000,000
输入保证道路之间没有形成环
时间：2 sec
空间：256MB
提示
拓扑排序
最后提交给那个OJ的代码：
#include<iostream>
#include <stdio.h>
#include <malloc.h>#define MAXSIZE 100002
#define TRUE 1
#define FALSE 0using namespace std;typedef int VertexData;
typedef int AdjType;//保存每个节点的最大路数
int Roads[MAXSIZE+1];
int maxRoad=0;typedef struct Stack //定义栈
{int data[MAXSIZE+1];int top;
}Stack;typedef struct ArcNode //定义弧结点
{AdjType adj;ArcNode *nextArc;
}ArcNode;typedef struct VertexNode //定义顶点
{VertexData vertexData;ArcNode *firstArc;
}VertexNode;typedef struct AdjMatrix //定义图
{VertexNode vertexNodes[MAXSIZE+1];int verNum,arcNum;
}AdjMatrix;//全局变量
int indegree[MAXSIZE+1]={0};int LocateGraph(AdjMatrix *g, VertexData vertexData)
{int iIndex;for(iIndex=1;iIndex<=g->verNum;iIndex++){if(vertexData==g->vertexNodes[iIndex].vertexData)return iIndex;}return FALSE;
}void CreateGraph(AdjMatrix *g)
{int iCount,arcStart,arcEnd;int start,end;//输入有向无环图的顶点,及弧数cin>>g->verNum>>g->arcNum;//输入有向无环图的顶点信息ArcNode *q=NULL;for(iCount=1;iCount<=g->verNum;iCount++){ g->vertexNodes[iCount].vertexData=iCount;g->vertexNodes[iCount].firstArc=NULL;}for(iCount=1;iCount<=g->arcNum;iCount++){//输入弧的起始与结束的信息cin>>start>>end;arcStart=LocateGraph(g,start);arcEnd=LocateGraph(g,end);//添加弧结点q=(ArcNode*)malloc(sizeof(ArcNode));q->adj=arcEnd;q->nextArc=g->vertexNodes[arcStart].firstArc;g->vertexNodes[arcStart].firstArc=q;//对于第arcEnd个顶点的入度值加1indegree[arcEnd]++;}
}//判栈空
int IsEmpty(Stack *stack)
{return stack->top==-1?TRUE:FALSE;
}//初始化栈
void InitStack(Stack *stack)
{stack->top=-1;
}//出栈
void Pop(Stack *stack,int *iIndex)
{*iIndex=stack->data[stack->top--];
}//进栈
void Push(Stack *stack,int value)
{stack->data[++stack->top]=value;
}//拓扑排序
void Tuopu(AdjMatrix *g)
{int iCount;Stack *stack=(Stack*)malloc(sizeof(Stack));InitStack(stack);ArcNode *p=NULL;//初始化 路数，都等于1for(iCount=1;iCount<=g->verNum;iCount++)Roads[iCount]=1;//对于入度为0的顶点入栈for(iCount=1;iCount<=g->verNum;iCount++){if(indegree[iCount]==0){Push(stack,iCount);}}//输出拓扑序列//输出顶点后，将与该顶点相连的顶点的边删除，将与相连顶点的入度减1，如减后为0，入栈，栈空结束while(!IsEmpty(stack)){Pop(stack,&iCount);//cout<<g->vertexNodes[iCount].vertexData<<" ";//这里处理路数p=g->vertexNodes[iCount].firstArc;while(p!=NULL){ if(--indegree[p->adj]==0)Push(stack,p->adj);if(Roads[g->vertexNodes[iCount].vertexData]+1>Roads[p->adj])Roads[p->adj]=Roads[g->vertexNodes[iCount].vertexData]+1;if(maxRoad<Roads[p->adj])maxRoad=Roads[p->adj];p=p->nextArc;}}//end while//cout<<endl;
}int main()
{AdjMatrix *g=(AdjMatrix*)malloc(sizeof(AdjMatrix));CreateGraph(g);Tuopu(g);printf("%d\n",maxRoad);return 0;
}
结果：
