目录
题目
给定一个有向无环图，叫你求图中的最长路径
思路
记忆化搜索，定义 f[i] : 表示从点i开始的最长路径长度，那么很容易得出转移方程为
\(f_i = max(f_i, f_j+1)\)，j为i的子节点
代码
点击查看代码
/*
* @Descripttion:
* @Author: Echo
* @version:
* @Date: 2022-08-29 17:04:52
* @LastEditors: Echo
* @LastEditTime: 2022-08-29 17:12:33
*/
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; ++i)
#define per(i, x, y) for (int i = x; i >= y; --i)
#define mem(a, b) memset(a, b, sizeof a)
#define INF 0x3f3f3f3f
#define ll long long
#define pushk push_back
using namespace std;
const int N = 1e5 + 9;
vector<int> g[N];
int f[N];
bool st[N];
void dfs(int u, int fa){
if(f[u]) return ;
for(auto & it : g[u]){
if(it!=fa){
dfs(it, u);
f[u] = max(f[u], f[it]+1);
}
}
}
int main()
{
int n, m;
cin >> n >> m;
rep(i, 1, m)
{
int u,v;
scanf("%d %d",&u,&v);
g[u].pushk(v);
}
rep(i,1,n){
if(!st[i]){
st[i] = 1;
f[0] = -1;
dfs(i,0);
}
}
int ans=0;
rep(i,1,n) ans=max(ans,f[i]);
cout<<ans;
return 0;
}