【BZOJ1093】[ZJOI2007]最大半联通子图（Tarjan，动态规划）
题面
题解
显然强连通分量对于题目是没有任何影响的，直接缩点就好了。
那么接下来剩下的是一个\(DAG\)，既然任意两点之间都有一条路径连接，在\(DAG\)上的体现就是这个玩意一定是一条链。随便\(dp\)一下就好了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define MAX 100100
#define MAXL 1000100
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
vector<int> E[MAX];
struct Line{int v,next;}e[MAXL];
int h[MAX],cnt=1;
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}
int dfn[MAX],low[MAX],S[MAX],G[MAX],sz[MAX],tim,top,gr,len[MAX];
int dg[MAX],p[MAX],f[MAX],g[MAX],tot;
bool ins[MAX];
void Tarjan(int u)
{
S[++top]=u;dfn[u]=low[u]=++tim;ins[u]=true;
for(int i=h[u];i;i=e[i].next)
if(!dfn[e[i].v])
Tarjan(e[i].v),low[u]=min(low[u],low[e[i].v]);
else if(ins[e[i].v])
low[u]=min(low[u],dfn[e[i].v]);
if(dfn[u]==low[u])
{
++gr;int v;
do{v=S[top--];ins[v]=false;G[v]=gr;++sz[gr];}while(u!=v);
}
}
void Topsort()
{
queue<int> Q;
for(int i=1;i<=gr;++i)if(!dg[i])Q.push(i),E[0].push_back(i),++len[0];
while(!Q.empty())
{
int u=Q.front();Q.pop();p[++tot]=u;
for(int i=0;i<len[u];++i)
if(!--dg[E[u][i]])Q.push(E[u][i]);
}
}
int n,m,MOD;
int main()
{
n=read();m=read();MOD=read();
for(int i=1,u,v;i<=m;++i)u=read(),v=read(),Add(u,v);
for(int i=1;i<=n;++i)if(!dfn[i])Tarjan(i);
for(int u=1;u<=n;++u)
for(int i=h[u];i;i=e[i].next)
if(G[u]!=G[e[i].v])
E[G[u]].push_back(G[e[i].v]);
for(int i=1;i<=gr;++i)sort(E[i].begin(),E[i].end());
for(int i=1;i<=gr;++i)len[i]=unique(E[i].begin(),E[i].end())-E[i].begin();
for(int i=1;i<=gr;++i)
for(int j=0;j<len[i];++j)
++dg[E[i][j]];
Topsort();
for(int i=gr;~i;--i)
{
int u=p[i];f[u]=sz[u];g[u]=1;
for(int j=0;j<len[u];++j)
{
int v=E[u][j];
if(f[u]<sz[u]+f[v])
f[u]=sz[u]+f[v],g[u]=g[v];
else if(f[u]==sz[u]+f[v])
g[u]=(g[u]+g[v])%MOD;
}
}
printf("%d\n%d\n",f[0],g[0]);
return 0;
}