最大半连通子图

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;

int n,m,mod;
int hd1[N],nt1[N],vr1[N],tt1;
int hd[N],nt[N],vr[N],tt;
int dfn[N],low[N],times;
bool ins[N];
stack<int> st;
int scc_size[N],id[N],scc_cnt;
int f[N],g[N],v[N],ans,tmp;

void add1(int x,int y)
{
	vr1[++tt1]=y;
	nt1[tt1]=hd1[x];
	hd1[x]=tt1;
}

void add(int x,int y)
{
	vr[++tt]=y;
	nt[tt]=hd[x];
	hd[x]=tt;
}

void tarjan(int x)
{
	dfn[x]=low[x]=++times;
	st.push(x);
	ins[x]=1;
	for(int i=hd1[x];i;i=nt1[i])
	{
		int y=vr1[i];
		if(!dfn[y]) 
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(ins[y])
		{
			low[x]=min(low[x],dfn[y]);
		}
	}
	if(low[x]==dfn[x])
	{
		scc_cnt++;
		int val;
		do
		{
			val=st.top();
			st.pop();
			ins[val]=0;
			id[val]=scc_cnt;
			scc_size[scc_cnt]++;
		}while(val!=x);
	} 
}

int main()
{
	scanf("%d%d%d",&n,&m,&mod);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add1(x,y);
	}
	for(int i=1;i<=n;i++)//tarjan 
		if(!dfn[i]) 
			tarjan(i);
	for(int x=1;x<=n;x++)//缩点 
	{
		//初始化 
		f[x]=scc_size[x];//最大半连通子图的大小 
		g[x]=1;//方案数 
		for(int i=hd1[x];i;i=nt1[i])
		{
			int y=vr1[i];
			int a=id[x],b=id[y];
			if(a==b) continue;
			add(a,b);
		}
	} 
	for(int x=scc_cnt;x>=1;x--) //缩点后的顺序为逆拓扑序 
	{
   		for(int i=hd[x];i;i=nt[i]) 
		{
	   		int y=vr[i];
	   		int w=f[x]+scc_size[y];
	   		if(v[y]==x) continue; //重边
	   		v[y]=x; //记录转移 
	   		if(f[y]<w) 
			{
	   			f[y]=w;
	   			g[y]=g[x];
	   		} 
			else if(f[y]==w) 
			{
	   			g[y]+=g[x];
	   			g[y]%=mod;
	   		}
   		}
	}
	for(int i=1;i<=scc_cnt;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);
	return 0;
}