洛谷2272 [ZJOI2007]最大半连通子图

题意

定义半连通图为对于 $\forall (u,v)$ ，存在从 $u$ 到 $v$ 或从 $v$ 到 $u$ 的有向路径。给出一个有向图，求最大半连通子图中的节点个数以及最大半连通子图的个数。

其中点数 $N\le 100000$ ，边数 $M\le 1000000$ 。

题解

显然连通图也属于半连通图，那么可以先缩点，记录每个点的新编号 $scc[]$ 以及包含节点个数 $siz[]$ ，并删去重边后重新建图。然后问题就转化为在有向无环图中求最长链。

考虑拓扑排序后dp，用 $tot[i]$ 记录终点为 $i$ 的链中节点个数，用 $sum[i]$ 记录终点为 $i$ 的最长链的个数，那么对于节点 $x$ ，枚举与它相连的节点 $y$ ，得到状态转移如下：

$$sum[y]=\begin{cases} sum[y]+sum[x],tot[y]=tot[x]+siz[y] \\ sum[x],tot[y]<tot[x]+siz[y]\end{cases}$$

$$tot[y]=\max(tot[y],tot[x]+siz[y])$$

最后统计答案时取节点个数的最大值，还有将节点个数同为最大的最长链个数累加起来即可。

#include<bits/stdc++.h>

using namespace std;

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

stack <int> s;
struct Edge {
    int next,to,from;
} edge[1000005],edge2[1000005],e[1000005];
int cnt,head[100005],cnt2,head2[100005],ecnt,n,m,ha,a,b;
int dfsord,scnt,id[100005],low[100005],scc[100005],siz[100005],in[100005],tot[100005],sum[100005];

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

inline void add2(int u,int v)
{
    edge2[++cnt2].to=v;
    edge2[cnt2].from=u;
    edge2[cnt2].next=head2[u];
    head2[u]=cnt2;
}

void dfs(int x)
{
    id[x]=low[x]=++dfsord;
    s.push(x);
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (!id[y])
        {
            dfs(y);
            low[x]=min(low[x],low[y]);
        }
        else if (!scc[y]) low[x]=min(low[x],id[y]);
    }
    if (id[x]==low[x])
    {
        scnt++;
        while (!s.empty())
        {
            int t=s.top(); s.pop();
            scc[t]=scnt;
            siz[scnt]++;
            if (t==x) break;
        }
    }
}

inline bool cmp(Edge x,Edge y) { return (x.from==y.from) ? x.to<y.to : x.from<y.from; }

inline void t_sort()
{
    queue <int> q;
    for (int i=1;i<=scnt;i++)
    {
        if (in[i]) continue;
        q.push(i);
        tot[i]=siz[i];
        sum[i]=1;
    }
    while (!q.empty())
    {
        int x=q.front(); q.pop();
        for (int i=head2[x];i;i=edge2[i].next)
        {
            int y=edge2[i].to;
            in[y]--;
            if (!in[y]) q.push(y);
            if (tot[y]==tot[x]+siz[y]) sum[y]=(sum[y]+sum[x])%ha;
            else if (tot[y]<tot[x]+siz[y])
            {
                tot[y]=tot[x]+siz[y];
                sum[y]=sum[x];
            }
        }
    }
}

int main()
{
    n=read(); m=read(); ha=read();
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read();
        add(a,b);
    }
    for (int i=1;i<=n;i++)
    {
        if (id[i]) continue;
        dfs(i);
    }
    for (int x=1;x<=n;x++)
    {
        for (int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to;
            if (scc[x]==scc[y]) continue;
            e[++ecnt].from=scc[x];
            e[ecnt].to=scc[y];
        }
    }
    sort(e+1,e+ecnt+1,cmp);
    for (int i=1;i<=ecnt;i++)
    {
        if (e[i].from==e[i-1].from && e[i].to==e[i-1].to) continue;
        add2(e[i].from,e[i].to);
        in[e[i].to]++;
    }
    t_sort();
    int ans=0,ans_sum=0;
    for (int i=1;i<=scnt;i++)
    {
        if (tot[i]>tot[ans])
        {
            ans=i;
            ans_sum=sum[i];
        }
        else if (tot[i]==tot[ans]) ans_sum=(ans_sum+sum[i])%ha;
    }
    printf("%d\n%d",tot[ans],ans_sum);
    return 0;
}