P3916 图的遍历

题目传送门

今晚闲游洛谷，在图论中发现了这独树一帜的记忆化搜索。看到这道题，第一感受就是DFS，每一个点DFS一遍，如果能更新就更新，但是这样的时间复杂度是O(nm)，对于1≤N,M≤10⁵的数据显然是承受不住的，会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;
}