【BZOJ1093】[ZJOI2007]最大半联通子图（Tarjan，动态规划）

题面

BZOJ

洛谷

洛谷的讨论里面有一个好看得多的题面

题解

显然强连通分量对于题目是没有任何影响的，直接缩点就好了。

那么接下来剩下的是一个\(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;

}