[BZOJ 1093][ZJOI 2007]最大半連通サブマップ強連通+トポロジーソート+dp作題ノート

テーマの出所:http://www.lydsy.com/JudgeOnline/problem.php?id=1093
Tarjanはsccを求め,縮点後の図走拓列は最長チェーンを求める.トポロジーツリーでdpを行います.トポロジー針は階層問題を行い,1つのノードを先に処理した前駆者がそのノードを処理し,後効性を除去したので,トポロジーツリー上でdpすることができる.注意SCC縮点後、エッジが重い場合は特審が必要になる可能性があります.

#include 
#include 
#include 
#include 
#include 
using namespace std;
int t=0,tot=1,n,m,mx=0,scc=0,ans=0,top=0,MOD;
const int N=100005,M=1000005;
int head[N],e[M<<1],ver[M<<1],next[M<<1];
int dfn[N],low[N],q[N<<1],bel[N],hav[N];
int ind[N],vis[N],f[N],g[N];
vector<int> G[N];
bool inq[N];
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void add (int u,int v) {
    ver[++tot]=v;next[tot]=head[u];head[u]=tot;
}

void Tarjan (int x) {
    dfn[x]=low[x]=++t;
    q[++top]=x; inq[x]=1;
    for (int i=head[x];i;i=next[i]) 
        if (!dfn[ver[i]])
            Tarjan(ver[i]),low[x]=min(low[x],low[ver[i]]);
        else if (inq[ver[i]]) low[x]=min(low[x],dfn[ver[i]]);
    int now=0;
    if (dfn[x]==low[x]) {
        scc++;
        while (now!=x) {
            now=q[top--];
            inq[now]=0;
            hav[scc]++;
            bel[now]=scc;
        }
    }
}

void rebuild () {
    for (int x=1;x<=n;x++) 
        for (int i=head[x];i;i=next[i])
            if (bel[x]!=bel[ver[i]])
                G[bel[x]].push_back(bel[ver[i]]),++ind[bel[ver[i]]];//
}

void dp () {
    queue<int> q;
    for (int i=1;i<=scc;i++) {
        if (!ind[i]) q.push(i);
        f[i]=hav[i]; g[i]=1;
    }
    while (!q.empty()) {
        int now=q.front();int v; q.pop();
        for (int i=0;iif (!ind[v]) q.push(v);
            if (vis[v]==now) continue;//       。
            if (f[now]+hav[v]>f[v]) {
                f[v]=f[now]+hav[v];
                g[v]=g[now];
            }
            else if (f[now]+hav[v]==f[v])
                g[v]=(g[v]+g[now])%MOD;
            vis[v]=now;
        }
    }   
}

int main () {
    int u,v;
    n=read(); m=read(); MOD=read();
    for (int i=1;i<=m;i++) {
        u=read(); v=read();
        add(u,v);
    }
    for (int i=1;i<=n;i++) if (!dfn[i]) Tarjan(i);
    rebuild();
    dp();
    for (int i=1;i<=scc;i++) {
        if (f[i]>mx)mx=f[i],ans=g[i];
        else if (f[i]==mx) ans=(ans+g[i])%MOD;
    }
    printf("%d
%d
",mx,ans);
    return 0;
}