60分求助!!最后一个点为什么RE了?

P2272 [ZJOI2007] 最大半连通子图

遮云壑 @ 2021-06-27 22:44:39

#include<bits/stdc++.h>
#define maxn 1000010
using namespace std;

inline void read(int& x)
{
    x=0;
    int y=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')y=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    x=x*y;
}

int n,m,mod;
struct edge{
    int to,next;
}e[maxn];

int cnt=0,head[10010];
inline void add(int u,int v)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}

int dfn[10010],low[10010],st[10010],top,ins[10010],tim;
int totscc,scc[10010],belong[10010];
void tarjan(int x)
{
    dfn[x]=low[x]=++tim;
    st[++top]=x;ins[x]=1;
    for(int i=head[x];i;i=e[i].next)
    {
        int y=e[i].to;
        if(dfn[y]==0)
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(ins[y])low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x])
    {
        totscc++;
        int k;
        do{
            k=st[top];top--;
            ins[k]=0;
            belong[k]=totscc;
            scc[totscc]++;
        }while(k!=x);
    }
}

int h[10010],cnt_;
edge ed[maxn];
inline void add_(int u,int v)
{
    ed[++cnt_].to=v;
    ed[cnt_].next=h[u];
    h[u]=cnt_;
}

struct node{
    int u,v;
    bool operator <(const node &x)const
    {
        if(u==x.u)return v<x.v;
        else return u<x.u;
    }
}a[maxn];
int in[10010],cntt;
inline void rebuild()
{
    for(int x=1;x<=n;x++)
    {
        for(int i=head[x];i;i=e[i].next)
        {
            int y=e[i].to;
            if(belong[x]!=belong[y])
            {
                a[++cntt].u=belong[x];
                a[cntt].v=belong[y];
            }
        }
    }
    sort(a+1,a+1+cntt);
    for(int i=1;i<=cntt;i++)
    {
        if((a[i].u==a[i-1].u)&&(a[i].v==a[i-1].v))continue;
        add_(a[i].u,a[i].v);
        in[a[i].v]++;
    }
}

int f[10010],Dp[10010];
queue<int> q;
inline void dp()
{
    for(int i=1;i<=totscc;i++)
    {
        if(in[i]==0)
        {
            q.push(i);
            f[i]=scc[i];
            Dp[i]=1;
        }
    }
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int i=h[x];i;i=ed[i].next)
        {
            int y=ed[i].to;
            if(f[y]==f[x]+scc[y])
            {
                Dp[y]+=Dp[x];
                Dp[x]%=mod;
            }
            if(f[y]<f[x]+scc[y])
            {
                f[y]=f[x]+scc[y];
                Dp[y]=Dp[x];
            }
            in[y]--;
            if(in[y]==0)q.push(y);
        }
    }
}

int main(){
    read(n),read(m),read(mod);
    int u,v;
    for(int i=1;i<=m;i++)
    {
        read(u),read(v);
        add(u,v);
    }
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==0)tarjan(i);
    }
    rebuild();
    dp();

    int ans1=0,ans2=0;
    for(int i=1;i<=totscc;i++)
    {
        if(f[i]>ans1)
        {
            ans1=f[i];
            ans2=Dp[i];
        }
        else if(f[i]==ans1)
        {
            ans2+=Dp[i];
            ans2%=mod;
        }
    }
    printf("%d\n%d\n",ans1,ans2);

    return 0;
}

|