NC20603 [ZJOI2007]最大半连通子图

题目：

• 一个有向图G=(V,E)称为半连通的(Semi-Connected)，如果满足：u,v∈V，满足u→v或v→u，即对于图中任意 两点u，v,存在一条u到v的有向路径或者从v到u的有向路径。
• 若G'=(V',E')满足V'∈V，E'是E中所有跟V'有关的边， 则称G'是G的一个导出子图。
• 若G'是G的导出子图，且G'半连通，则称G'为G的半连通子图。
• 若G'是G所有半连通子图 中包含节点数最多的，则称G'是G的最大半连通子图。
• 给定一个有向图G，请求出G的最大半连通子图拥有的节点数K ，以及不同的最大半连通子图
的数目C。由于C可能比较大，仅要求输出C对X的余数。

题解：

• 如果两点互相可以到达，那么它们必是半连通图，所以考虑先Tarjan缩点，接着去除重边重新建图，你会发现，在这个有向无环图（DAG）中，半连通子图都是一条链（可以举反例试试，这条链不可能有分支，否则将有两点无法抵达另一方）
• 于是，G的最大半连通子图拥有的节点数K就是最长链长度，不同的最大半连通子图的数目就是最长链个数。
• 最长链可以直接用拓扑排序（topo），最长链个数用一个类似DP的方法，用f【i】表示以 i为终点的方案数，那么f【i】就等于满足距离为起点到 i 的临时最短距离的点的 f 的和。然后查找距离等于最长链的点，答案为它们的方案数之和

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10,maxm=1e6+10;
struct edge
{
    int u,v,nxt;
}e[maxm],ee[maxm];
int head[maxn],js,headd[maxn],jss;
void addage(edge e[],int head[],int &js,int u,int v)
{
    e[++js].u=u;e[js].v=v;
    e[js].nxt=head[u];head[u]=js;
}
int dfn[maxn],low[maxn],cnt,st[maxn],top,lt[maxn],lts,ltn[maxn];
void  tarjan(int u)
{
    dfn[u]=low[u]=++cnt;
    st[++top]=u;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!lt[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        lt[u]=++lts;ltn[lts]++;
        while(st[top]!=u)lt[st[top--]]=lts,ltn[lts]++;
        --top;
    }
}
int n,m,x;
int f[maxn],ff[maxn];
int cd[maxn],rd[maxn];
int maxd,maxf;
int pc[maxn];
queue<int>q;
void dfs()
{
    while(!q.empty())
    {
        int u=q.front();q.pop();
        maxd=max(maxd,f[u]);
        for(int i=headd[u];i;i=ee[i].nxt)
        {
            int v=ee[i].v;
            rd[v]--;
            if(rd[v]==0)q.push(v);
            if(pc[v]==u)continue;
            if(f[u]+ltn[v]>f[v])
            {
                f[v]=f[u]+ltn[v];
                ff[v]=ff[u];

            }
            else if(f[u]+ltn[v]==f[v])
            {
                ff[v]=(ff[u]+ff[v])%x;
            }
            pc[v]=u;
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&x);
    for(int u,v,i=1;i<=m;++i)
    {
        scanf("%d%d",&u,&v);
        addage(e,head,js,u,v);
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i])tarjan(i);
    for(int u=1;u<=n;++u)
        for(int i=head[u];i;i=e[i].nxt)
            if(lt[e[i].u]!=lt[e[i].v])addage(ee,headd,jss,lt[e[i].u],lt[e[i].v]),cd[lt[e[i].u]]++,rd[lt[e[i].v]]++;
    for(int i=1;i<=lts;++i)
        if(rd[i]==0)q.push(i),f[i]=ltn[i],ff[i]=1;
    dfs();
    for(int i=1;i<=lts;++i)
    {
        if(f[i]==maxd)maxf=(maxf+ff[i])%x;
    }
    printf("%d\n%d\n",maxd,maxf);
    return 0;
}