数据结构作业六 旅行商（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;
}