bzoj 1093 [ ZJOI 2007 ] 最大半连通子图 —— 拓扑+DP

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1093

先缩点，然后就是找最长链，DP一下即可；

注意缩点后的重边！会导致重复计算答案。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const maxn=1e5+,maxm=1e6+;

int n,m,mod,hd[maxn],ct,col[maxn],cr,tim,dfn[maxn],low[maxn],sta[maxn],top,h,t;

int f[maxn],s[maxn],siz[maxn],deg[maxn],ans,mk[maxn];

ll cnt;

bool vis[maxn];

struct N{

    int fr,to,nxt;

    N(int f=,int t=,int n=):fr(f),to(t),nxt(n) {}

}ed[maxm];

void add(int x,int y){ed[++ct]=N(x,y,hd[x]); hd[x]=ct;}

//void add2(int x,int y){edge[++xt]=N(y,head[x]); head[x]=xt;}

int rd()

{

    int ret=,f=; char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}

    while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

    return ret*f;

}

void tarjan(int x)

{

    dfn[x]=low[x]=++tim;

    sta[++top]=x; vis[x]=;

    for(int i=hd[x],u;i;i=ed[i].nxt)

    {

        if(!dfn[u=ed[i].to])tarjan(u),low[x]=min(low[x],low[u]);

        else if(vis[u])low[x]=min(low[x],dfn[u]);

    }

    if(low[x]==dfn[x])

    {

        cr++; int y;

        while((y=sta[top])!=x)col[y]=cr,vis[y]=,siz[cr]++,top--;

        col[x]=cr; vis[x]=; siz[cr]++; top--;

    }

}

void topo()

{

//    for(int i=1;i<=cr;i++)

//        if(!deg[i])q.push(i),f[i]=siz[i],s[i]=1;

    h=; t=;

    for(int i=;i<=cr;i++)

        if(!deg[i])sta[++t]=i,f[i]=siz[i],s[i]=;

    while(h<=t)

    {

//        int x=q.front(); q.pop();

        int x=sta[h]; h++;

        for(int i=hd[x],u;i;i=ed[i].nxt)

        {

            deg[u=ed[i].to]--; if(!deg[u])sta[++t]=u;//

            if(mk[u]==x)continue;//注意处理连通块之间的重边！

            if(f[u]<f[x]+siz[u])f[u]=f[x]+siz[u],s[u]=s[x];

            else if(f[u]==f[x]+siz[u])s[u]=(s[u]+s[x])%mod;

            mk[u]=x;

        }

    }

}

int main()

{

    n=rd(); m=rd(); mod=rd();

    for(int i=,x,y;i<=m;i++)

    {

        x=rd(); y=rd();

        add(x,y);

    }

    for(int i=;i<=n;i++)

        if(!dfn[i])tarjan(i);

    ct=; memset(hd,,sizeof hd);

    for(int i=;i<=m;i++)

    {

        int u=ed[i].fr,v=ed[i].to;

        if(col[u]==col[v])continue;

        add(col[u],col[v]); deg[col[v]]++;

    }

//    for(int i=1;i<=n;i++)

//        for(int j=hd[i],u;j;j=ed[j].nxt)

//        {

//            if(col[i]==col[u=ed[j].to])continue;

//            add2(col[i],col[u]); deg[col[u]]++;

//        }

    topo();

    for(int i=;i<=cr;i++)

    {

        if(f[i]>ans)ans=f[i],cnt=s[i];

        else if(f[i]==ans)(cnt+=s[i])%=mod;

    }

    printf("%d\n%lld\n",ans,cnt);

    return ;

}