数据结构作业六 旅行商（TSP）
目录
图论第一次作业，不需要提交报告，在OJ上提交。
描述
Shrek是一个大山里的邮递员，每天负责给所在地区的n个村庄派发信件。但杯具的是，由于道路狭窄，年久失修，村庄间的道路都只能单向通过，甚至有些村庄无法从任意一个村庄到达。这样我们只能希望尽可能多的村庄可以收到投递的信件。
Shrek希望知道如何选定一个村庄A作为起点（我们将他空投到该村庄），依次经过尽可能多的村庄，路途中的每个村庄都经过仅一次，最终到达终点村庄B，完成整个送信过程。这个任务交给你来完成。
输入
第一行包括两个整数n，m，分别表示村庄的个数以及可以通行的道路的数目。
以下共m行，每行用两个整数v1和v2表示一条道路，两个整数分别为道路连接的村庄号，道路的方向为从v1至v2，n个村庄编号为[1, n]。
1 ≤ n ≤ 1,000,000
0 ≤ m ≤ 1,000,000
输入保证道路之间没有形成环
输出
输出一个数字，表示符合条件的最长道路经过的村庄数。
输入样例 1
4 3
1 4
2 4
4 3
输出样例 1
3
代码
先进性拓扑排序，之后dp找到最大值。
#include<iostream>
using namespace std;
#define myMax(x,y) ((x) > (y) ? (x) : (y))
int inDeg[1000005] = {0}; //入度 用于拓扑排序
int tpSorted[1000005] = {0}; //拓扑排序的顺序
//单个村庄
struct village{
int id;
village * next_village;
village(int _id, village* next = NULL):id(_id),next_village(next){}
};
struct villages{
village* _next;
int dp; //直接写入属性
villages():_next(NULL), dp(1){}
void add(int next_id);
}Villages[1000005];
void villages::add(int next_id){
inDeg[next_id] ++;
if(!_next){
_next = new village(next_id);
}
else{
_next = new village(next_id, _next);
}
}
//全局变量真好用...
int topologicalSort(int n){
int res = 0; //记录最大值
int size = 0; //拓扑数组长度
for(int i = 1; i <= n; i++)
if(!inDeg[i])
tpSorted[size++] = i;
//对数组进行操作
for(int i = 0; i < size; i++){
village* cur = Villages[tpSorted[i]]._next;
while(cur){
Villages[cur->id].dp = myMax(Villages[tpSorted[i]].dp+1, Villages[cur->id].dp);
res = myMax(Villages[cur->id].dp, res);
inDeg[cur->id]--;
if(!inDeg[cur->id])
tpSorted[size++] = cur->id;
cur = cur->next_village;
}
}
return res;
}
int main(){
int n, m, v1, v2;
cin >> n >> m;
while(m--){
cin >> v1 >> v2;
Villages[v1].add(v2);
}
cout << topologicalSort(n) << endl;
return 0;
}