自动搬运

查看原文

来自洛谷，原作者为

	xiaofulll It's me~

搬运于2025-08-24 21:35:49，当前版本为作者最后更新于2019-09-05 16:59:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我写这篇题解主要是为了两个trick：

1. Tarjan缩点后的点的排列顺序是逆拓扑序，所以不需要对新图进行拓扑排序

可以随机拍几组数据看一下 

证明过程略

主要是我也不会

2. 拓扑序DP下的判重边：

只需要记录一下每一个点上一次是由谁转移而来的就好

如上，缩点后的代码就可以这样写：
（HEAD、VER、NEXT：新图的前向星；size：每个强
连通分量包含的点数；f：最大半连通子图的大
小；g：方案数）

   for(int x=scc;x>=1;x--) {					//缩点后的顺序为逆拓扑序 
   	for(int i=HEAD[x];i;i=NEXT[i]) {
   		int y=VER[i];
   		if(used[y]==x) continue;			//重边 
   		used[y]=x;					//记录转移 
   		if(f[y]<f[x]+size[y]) {
   			f[y]=f[x]+size[y];
   			g[y]=g[x];
   		}else if(f[y]==f[x]+size[y]) {
   			g[y]+=g[x];
   			g[y]%=MOD;
   		}
   	}
   }

附最终结果： 总用时：280ms

其他的就是常规的缩点和答案统计了

最后附上全部代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+2,M=2e6+2;
int n,m,tot,MOD,top,num,scc,TOT,Head[N],ver[M],Next[M],dfn[N],low[N],Stack[N],belong[N];
int size[N],HEAD[N],VER[M],NEXT[M],f[N],g[N],used[N];
bool instack[N];
 
inline int read() {
	int x=0;char y='*',z=getchar();
	while(z<'0'||z>'9') y=z,z=getchar();
	while(z>='0'&&z<='9') x=(x<<3)+(x<<1)+(z^48),z=getchar();
	return y=='-'?-x:x;
}
inline void add(int x,int y) {
	ver[++tot]=y;
	Next[tot]=Head[x];
	Head[x]=tot;
}
inline void ADD(int x,int y) {
	VER[++TOT]=y;
	NEXT[TOT]=HEAD[x];
	HEAD[x]=TOT;
}
inline void Tarjan(int x) {
	dfn[x]=low[x]=++num;
	Stack[++top]=x;
	instack[x]=true;
	for(int i=Head[x];i;i=Next[i]) {
		int y=ver[i];
		if(!dfn[y]) {
			Tarjan(y);
			low[x]=min(low[x],low[y]);
		}else if(instack[y]) {
			low[x]=min(low[x],low[y]);
		}
	}
	if(dfn[x]==low[x]) {
		scc++;
		int k=-1;
		while(k!=x) {
			k=Stack[top--];
			belong[k]=scc;
			size[scc]++;
			instack[k]=false;
		}
	}
}
int main() {
//	freopen("test.txt","r",stdin);
	n=read();m=read();MOD=read();
	for(int i=1,x,y;i<=m;i++) {
		x=read(); y=read();
		add(x,y);
	}
	for(int i=1;i<=n;i++) {
		if(!dfn[i]) {
			Tarjan(i);
		}
	}
	for(int x=1;x<=n;x++) {
		f[x]=size[x];
		g[x]=1;
		for(int i=Head[x];i;i=Next[i]) {
			int y=ver[i];
			if(belong[x]==belong[y]) continue;
			ADD(belong[x],belong[y]);
		}
	}
	for(int x=scc;x>=1;x--) {					//缩点后的顺序为逆拓扑序 
		for(int i=HEAD[x];i;i=NEXT[i]) {
			int y=VER[i];
			if(used[y]==x) continue;			//重边 
			used[y]=x;							//记录转移 
			if(f[y]<f[x]+size[y]) {
				f[y]=f[x]+size[y];
				g[y]=g[x];
			}else if(f[y]==f[x]+size[y]) {
				g[y]+=g[x];
				g[y]%=MOD;
			}
		}
	}
	int ans=0,tmp=0;
	for(int i=1;i<=scc;i++) {
		if(f[i]>ans) {
			ans=f[i];
			tmp=g[i];
		}else if(f[i]==ans) {
			tmp+=g[i];
			tmp%=MOD;
		}
	}
	printf("%d\n%d",ans,tmp);
}