Longest Path 题解

lottle1212 · 2023-03-14 19:35:39 · 题解

原题传送门

Part0：

题目大意：

给出一棵 N 个顶点 M 条边的有向无环图。
求该图最长路长度，即最长路径的边数。

样例输入：

样例输出：

如图，最长路径为 \{1,3,2,4\}，该路径边的数量为 3。

Part1：

首先，由于 N \leq 10^{5} ，我们可以知道该题时间复杂度为 O(n)。也就是说，将每一个点都遍历一遍。

由于该题为有向无环图，因此我们可以按序去搜索遍历每一个点。若该点未被访问过，则对其进行搜索；否则，就可以直接对该点保存的答案进行求最大。

AC Code：

#include<bits/stdc++.h>
using namespace std;
int ans,dp[100010],n,m,x,y,i,cnt,head[100010];
struct Edge{int next,to;}e[100010];//邻接表
void add(int x,int y){e[++cnt]={head[x],y};head[x]=cnt;}//邻接表建边
void dfs(int u){
    if(dp[u]) return ;//已经访问过，无需再次搜索
    int i,v;dp[u]=-1;
    for(i=head[u];i;i=e[i].next){
        v=e[i].to;
        dfs(v);
        dp[u]=max(dp[u],dp[v]);//在儿子的边数中求最大
    }
    ++dp[u];//加上自己与儿子的这条边
    ans=max(ans,dp[u]);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    while(m--) cin>>x>>y,add(x,y);//建边
    for(i=1;i<=n;i++) dfs(i);//搜索
    cout<<ans;
    return 0;
}