今晚闲游洛谷，在图论中发现了这独树一帜的记忆化搜索。看到这道题，第一感受就是DFS，每一个点DFS一遍，如果能更新就更新，但是这样的时间复杂度是O(nm)，对于1≤N,M≤105的数据显然是承受不住的，会T飞掉~
究其原因，是因为不断地更新，浪费了大量的时间。有没有改进的方法？？？答案是肯定的。
反向建边
反向建边可以让我们直接从最大的搜，只要最大的能搜到的一定都可以走到最大的，它的答案自然也就是最大的了，之后也就无需进行更新了，然后从最大的往小搜，可以达到下界O(n);
参考程序如下：
#include<iostream>
#include<cstring>
using namespace std;
int maxn[100001],n,m,v[100001],nxt[100001],head[100001],total,b1,b2,x,y;
void add()
{
cin>>b1>>b2;
total++;
nxt[total]=head[b2];
head[b2]=total;
v[total]=b1;
}
void dfs(int now,int begin)
{
if(maxn[now])return;
maxn[now]=begin;
for(int i=head[now];i!=-1;i=nxt[i])
{
dfs(v[i],begin);
}
}
int main()
{
memset(head,-1,sizeof(head));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
add();
}
for(int i=n;i>=1;i--)
{
dfs(i,i);
}
for(int i=1;i<=n;i++)cout<<maxn[i]<<" ";
cout<<endl;
}
原文：https://www.cnblogs.com/szmssf/p/10999932.html