tarjan求调玄关在线等,急!

P2272 [ZJOI2007] 最大半连通子图

sunqihuan @ 2024-12-12 22:25:38

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,dfn[N],low[N],scc,top,num,st[N],inst[N],belong[N],number[N],dp[N],cnt[N],du[N],mod;
vector<int> g[N],gg[N];
void tarjan(int u){
    dfn[u]=low[u]=++num;
    st[++top]=u;
    inst[u]=0;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(dfn[v]==0){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(inst[v]==1){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        scc++;
        int now;
        do{
            now=st[top--];
            inst[now]=0;
            belong[now]=scc;
            number[scc]++;
        }while(now!=u);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>mod;
    for(int i=1;i<=n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
        if(dfn[i]==0)tarjan(i);
    }
    set<int> S;
    for(int i=1;i<=n;i++){
        for(int j=0;j<g[i].size();j++){
            int v=g[i][j];
            int s1=belong[i],s2=belong[v];
            int hash=s1*1000000ll+s2;
            if(s1!=s2 && !S.count(hash)){
                gg[s1].push_back(s2);
                S.insert(hash);
            }
        }
    }
    for(int i=scc;i>=1;i--){
        if(!dp[i]){
            dp[i]=number[i];
            cnt[i]=1;
        }
        for(int j=0;j<gg[i].size();j++){
            int v=g[i][j];
            if(dp[v]<dp[i]+number[v]){
                dp[v]=dp[i]+number[v];
                cnt[v]=cnt[i];
            }else if(dp[v]==dp[i]+number[v]){
                cnt[v]=(cnt[v]+cnt[i])%mod;
            }
        }
    }
    int maxn=0,sum=0;
    for(int i=1;i<=scc;i++){
        if(dp[i]>maxn){
            maxn=dp[i];
            sum=cnt[i];
        }else if(dp[i]==maxn)sum=(sum+cnt[i])%mod;
    }
    cout<<maxn<<endl<<sum;
    return 0;
}

输出错误


|