玄关 kosaraju vector存图 60pts WA1,4,5,7
查看原帖
玄关 kosaraju vector存图 60pts WA1,4,5,7
1122611
stickman_stickmin楼主2024/6/30 17:34

如标题,自己造的几个数据都过了,查代码查不到什么问题 求助dalao

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e5+10;
vector<int>G[N],rG[N],scc[N];
//    正图   反图   连通分量图
vector<int>S;//存储第一次dfs结果,标记点的先后顺序
int vis[N],sccid[N],numscc;
//    节点所在scc序号
int a[N],u[N],v[N],w[N];
//             
int ans=-1,dp[N];
void dfs1(int u){
    if(vis[u])return;
    vis[u]=1;
    for(int i=0;i<G[u].size();i++)dfs1(G[u][i]);
    S.push_back(u);//最后再压入自己
}
void dfs2(int u){
    if(sccid[u])return;
    sccid[u]=numscc;
    w[numscc]+=a[u];
    for(int i=0;i<rG[u].size();i++)dfs2(rG[u][i]);
}
void kosaraju(int n){
    numscc=0;S.clear();
    memset(sccid,0,sizeof(sccid));
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)dfs1(i);
    for(int i=n-1;i>=0;i--){
        if(!sccid[S[i]]){
            numscc++; dfs2(S[i]);//有限递归栈顶元素
        }
    }
}
void dfs3(int u){
    if(dp[u])return;
    for(int i=0;i<scc[u].size();i++){
        if(dp[scc[u][i]])continue;
        dfs3(scc[u][i]);
        dp[u]=max(dp[u],dp[scc[u][i]]);
    }
    dp[u]+=w[u];
}
int main(){
//freopen("P3387_1.in","r",stdin);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i];
        G[u[i]].push_back(v[i]);
        rG[v[i]].push_back(u[i]);
    }
    kosaraju(n);
    
    for(int i=1;i<=m;i++){
        if(sccid[u[i]]!=sccid[v[i]]){
            scc[sccid[u[i]]].push_back(sccid[v[i]]);
        }
    }
    for(int i=1;i<=numscc;i++){
        if(dp[i])continue;
        dfs3(i);
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}
2024/6/30 17:34
加载中...