Tarjan强连通分量缩点

P3387 【模板】缩点
先tarjan 缩点，然后重构图，用map消除重复边，之后记忆化搜索，reutrn maxx;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
typedef std :: pair<int,int> PII;
const int N = 1e5+9;
struct node
{
    int from,to;
}edge[N];
int idx,e[N],ne[N],w[N],h[N],w2[N];
int dfn[N],low[N];
int timestamp;
int stk[N];
int vis[N];
int id[N],scc_cnt;
bool in_stk[N];
int top;
int out[N];
int n,m;
int dp[N];
PII st[N];
std :: map<PII,int> mp;
void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u,in_stk[u] = true;
    for(int i=h[u]; ~i; i=ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u] = std :: min(low[u],low[j]);
        }
        else if(in_stk[j])
        {
            low[u] = std :: min(low[u],dfn[j]);
        }
    }
    if(dfn[u] == low[u])
    {
        ++scc_cnt;
        int y;
        do
        {
            y = stk[top--];
            in_stk[y] = false;
            id[y] = scc_cnt;
        }
        while(y != u);

    }
}
int dfs(int u)
{
    if(~dp[u]) return dp[u];
    dp[u] = w[u];
    int maxx = 0;
    for(int i=h[u]; ~i; i=ne[i])
    {
        int j = e[i];
        maxx = std :: max(maxx,dfs(j));
        dp[u] = maxx;
    }
    return dp[u] = maxx + w[u];
}

int main()
{
    memset(h,-1,sizeof h);
    memset(dp,-1,sizeof dp);
    std :: cin >> n >> m;
    for(int i=1; i<=n; i++) std :: cin >> w[i];
    for(int i=1; i<=m; i++)
    {
        int a,b;
        std :: cin >> a >> b;
        edge[i].from = a,edge[i].to = b;
        add(a,b);
    }
    for(int i=1; i<=n; i++)
    {
        if(!dfn[i]) tarjan(i);
    }
    for(int i=1; i<=n; i++)
    {
        w2[id[i]] += w[i];
    }
    for(int i=1; i<=n; i++) w[i] = w2[i];
    memset(h,-1,sizeof h);
    memset(dp,-1,sizeof dp);
    idx = 0;
    for(int i=1; i<=m; i++)
    {
        int a = edge[i].from,b = edge[i].to;
        if(id[a] == id[b] || mp[{id[a],id[b]}]) continue;
        mp[{id[a],id[b]}] = 1;
        add(id[a],id[b]);
    }
    int ans = 0;
    for(int i=1; i<=scc_cnt; i++)
    {
        if(!vis[i]) ans = std :: max(ans,dfs(i));
    }
    std :: cout<<ans<<"\n";
    return 0;
}