递归爆内存 MLE

错误的代码：：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long

struct node{
    int to;
    int next;
};
node edge[200010];
int cnt;
int head[100010];
int from[200010];
int to[200010];
bool vis[100010];
int p[100010];
int n,m;
int u;
int v[100010];
int f[100010];
int mv;

void addedge(int from,int to,node edge[],int head[],int &cnt){
    ++cnt;
    edge[cnt].to=to;
    edge[cnt].next=head[from];
    head[from]=cnt;
    return ;
}

void dfsf(int x){
    vis[x]=1;
    for(int k=head[x];k!=0;k=edge[k].next){
        if(!vis[edge[k].to]){
            dfsf(edge[k].to);
        }
    }
    p[--u]=x;
    return ;
}

void dfs(int x,int fa){
    vis[x]=0;
    f[x]=fa;
    if(v[x]>mv){
        mv=v[x];
    }
    for(int k=head[x];k!=0;k=edge[k].next){
        if(vis[edge[k].to]){
            dfs(edge[k].to,fa);
        }
    }
    return ;
}

int dfsv(int x){
    if(p[x]!=-1){
        return p[x];
    }
    int maxv=v[x];
    for(int k=head[x];k!=0;k=edge[k].next){
        maxv=max(maxv,dfsv(edge[k].to));
    }
    p[x]=maxv;
    return maxv;
}

int main(){
    int t;
    cin>>t;
    while(t--){
        cnt=0;
        memset(vis,0,sizeof(vis));
        memset(head,0,sizeof(head));
        cin>>n>>m;
        u=m;
        for(int i=1;i<=n;i++){
            scanf("%d",&v[i]);
        }
        for(int i=1;i<=n;i++){
            scanf("%d%d",&from[i],&to[i]);
            addedge(to[i],from[i],edge,head,cnt);
        }
        for(int i=1;i<=n;i++){
            if(!vis[i]){
                dfsf(i);
            }
        }
        cnt=0;
        memset(head,0,sizeof(head));
        for(int i=1;i<=m;i++){
            addedge(from[i],to[i],edge,head,cnt);
        }
        // //test::
        // for(int i=0;i<n;i++){
        //  cout<<p[i]<<" ";
        // }
        // cout<<endl;
        for(int i=0;i<n;i++){
            if(vis[p[i]]){
                mv=v[p[i]];
                // cout<<mv<<" ";
                dfs(p[i],p[i]);
                v[p[i]]=mv;
                // cout<<"MV::"<<mv<<endl;
            }
        }
        // for(int i=1;i<=n;i++){
        //  cout<<f[i]<<" ";
        // }
        // cout<<endl;
        cnt=0;
        memset(head,0,sizeof(head));
        for(int i=1;i<m;i++){
            if(f[from[i]]!=f[to[i]]){
                addedge(f[from[i]],f[to[i]],edge,head,cnt);
            }
        }
        memset(p,-1,sizeof(p));
        for(int i=1;i<=n;i++){
            cout<<dfsv(f[i])<<endl;
        }
    }
    return 0;
}

以上代码会超过空间，因为递归层数不低，空间占用大

解决方式：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long

const int uppern=1e5+5;
const int upperm=2e5+5;

int n,m;
struct node{
    int to;
    int next;
} edge[upperm];
int head[uppern];
int from[upperm];
int to[upperm];
int p[uppern];
int v[uppern];
int f[uppern];
bool vis[uppern];
int cnt;
int u;

void addedge(int from,int to){
    edge[++cnt].to=to;
    edge[cnt].next=head[from];
    head[from]=cnt;
    return ;
}

void fdfs(int x){
    vis[x]=1;
    for(int k=head[x];k!=0;k=edge[k].next){
        if(!vis[edge[k].to]){
            fdfs(edge[k].to);
        }
    }
    p[u--]=x;
    return ;
}

void dfs(int x,int fa){
    vis[x]=0;
    f[x]=fa;
    for(int k=head[x];k!=0;k=edge[k].next){
        if(vis[edge[k].to]){
            dfs(edge[k].to,fa);
        }
    }
    v[fa]=max(v[fa],v[x]);
    return ;
}

void dfsans(int x){
    // vis[x]=1;
    // x=f[x];
    if(vis[x]){
        return ;
    }
    vis[x]=1;
    for(int k=head[x];k!=0;k=edge[k].next){
        if(!vis[edge[k].to]){
            dfsans(edge[k].to);
        }
        p[x]=max(p[x],p[edge[k].to]);
    }
    p[x]=max(v[x],p[x]);
    return ;
}

void solve(){
    memset(head,0,sizeof(head));
    memset(vis,0,sizeof(vis));
    cin>>n>>m;
    cnt=0;
    u=n;
    for(int i=1;i<=n;i++){
        scanf("%d",&v[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&from[i],&to[i]);
        addedge(to[i],from[i]);
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]) fdfs(i);
    }
    // //test:::p
    // for(int i=1;i<=n;i++){
    //  cout<<p[i]<<" ";
    // }
    // cout<<endl;
    cnt=0;
    memset(head,0,sizeof(head));
    for(int i=1;i<=m;i++){
        addedge(from[i],to[i]);
    }
    for(int i=1;i<=n;i++){
        if(vis[p[i]]) dfs(p[i],p[i]);
    }
    cnt=0;
    memset(head,0,sizeof(head));
    for(int i=1;i<=m;i++){
        if(f[from[i]]!=f[to[i]]){
            addedge(f[from[i]],f[to[i]]);
        }
    }
    memset(p,0,sizeof(p));
    // for(int i=1;i<=n;i++){
    //  cout<<vis[i]<<" ";
    // }
    // cout<<endl;
    for(int i=1;i<=n;i++){
        if(!vis[f[i]]) dfsans(f[i]);
        printf("%d\n",p[f[i]]);
    }
    return ;
}

int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

注意cout特别慢