洛谷 1137旅行计划

拓扑排序

拓扑排序是针对二元组u（x,y)的变量x,y进行排序的算法。对于二元关系u（x,y），使得每一个y都排在x的后面。这种问题就称为拓扑排序。

关于拓扑排序的模板

拓扑排序完全可以使用dfs的方式去排序。由于采用dfs，可以满足如下几点：

1.满足所有二元关系前键在后键之前。

2.满足利用栈帧去判断是否有回路。

因此，利用dfs的方式去判断是一个极好的判断方法。

下面是拓扑排序的刘汝佳版代码。

int c[maxn];
int topo[maxn], t;
bool dfs(int u){
c[u] = -1; //访问标志
for(int v = 0; v < n; v++) if(G[u][v]) {
if(c[v]<0) return false; //存在有向环，失败退出
else if(!c[v] && !dfs(v)) return false;
}
c[u] = 1; topo[——t]=u;
return true;
}
bool toposort( ){
t = n;
memset(c, 0, sizeof(c));
for(int u = 0; u < n; u++) if(!c[u])
if(!dfs(u)) return false;
return true;
}

这里用到了一个c数组，c[u]=0表示从来没有访问过（从来没有调用过dfs(u)）；c[u]=1表
示已经访问过，并且还递归访问过它的所有子孙（即dfs(u)曾被调用过，并已返回）；c[u]=-
1表示正在访问（即递归调用dfs(u)正在栈帧中，尚未返回）。

关于本题的题目以及思路

本题的题意是，给你一个有向无环图，也就是DAG图，让你求对于图中的每个顶点，以此顶点为终点的最长路径。

本题应采用动态规划。

为什么我们需要将本问题进行拓扑排序呢？因为我们通过思考可以发现，只有通过拓扑排序，我们才能将整个图的状态按照时序进行排序。什么意思呢，就是将访问的点按照时间顺序排序。因此，才能用一个一维的dp【i】，以i作为状态，dp【i】表示当前状态下的最长路径。因为这样才能满足无后效性。也就是说，将节点排序后，才能经过线性时间进行动态规划。

这道题也是经典的DAG图上的动态规划问题。

本题的代码

//p1137 拓扑排序
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

const int maxn = 100000+5;
int n, m,t;
vector<vector<int>> G;
int dp[maxn],done[maxn];
int topo[maxn];

void dfs(int u) {
	for (int i = 0; i < G[u].size(); i++) {
		if (done[G[u][i]]) continue;
		dfs(G[u][i]);
	}
	done[u] = 1;
	topo[--t] = u;
}

int main() {
	cin >> n >> m; t = n;
	G.resize(n + 1);
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x>> y;
		G[x].push_back(y);
	}
	for (int i = 1; i <= n; i++) {
		if(!done[i]) dfs(i);
	}
	for (int i = 0; i <= n; i++) dp[i] = 1;
	for (int i = 0; i < n; i++) {
		int p = topo[i];
		for (int i = 0; i < G[p].size(); i++) {
			dp[G[p][i]] = max(dp[G[p][i]], dp[p] + 1);
		}
	}

	for (int i = 1; i <= n; i++) {
		cout << dp[i] << endl;
	}
}