标签：tarjan缩点，DP，拓扑排序
Description
一个有向图G=(V,E)称为半连通的(Semi-Connected)，如果满足：?u,v∈V，满足u→v或v→u，即对于图中任意
两点u，v,存在一条u到v的有向路径或者从v到u的有向路径。若G'=(V',E')满足V'?V，E'是E中所有跟V'有关的边，
则称G'是G的一个导出子图。若G'是G的导出子图，且G'半连通，则称G'为G的半连通子图。若G'是G所有半连通子图
中包含节点数最多的，则称G'是G的最大半连通子图。给定一个有向图G，请求出G的最大半连通子图拥有的节点数K
，以及不同的最大半连通子图的数目C。由于C可能比较大，仅要求输出C对X的余数。
Input
第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述接下来M行，每行两个正整
数a, b，表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。N ≤1
00000, M ≤1000000；对于100%的数据， X≤10^8
Output
应包含两行，第一行包含一个整数K。第二行包含整数C Mod X.
Sample Input
6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4
Sample Output
3
3
分析：先tarjan缩点，之后重建一个图，然后DP和拓扑排序跑最长链
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline LL read()
{
LL f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e5+6,maxm=2e6+6;
int mx,ans,ind,cnt,scc,top,m,n,mod;
int head[maxn],head2[maxn],dfn[maxn],low[maxn],hav[maxn],belong[maxn];
int r[maxn],f[maxn],g[maxn],vis[maxn],q[maxn];
bool inq[maxn];
struct edge{int to,next;}e[maxm],ed[maxm];
void tarjan(int x)
{
dfn[x]=low[x]=++ind;
q[++top]=x;inq[x]=1;
#define reg(x) for(int i=head[x];i;i=e[i].next)
#define v e[i].to
reg(x)
if(!dfn[v])tarjan(v),low[x]=min(low[x],low[v]);
else if(inq[v])low[x]=min(low[x],dfn[v]);
int now=0;
if(low[x]==dfn[x]){
scc++;
while(now!=x){
now=q[top];top--;
inq[now]=0;
hav[scc]++;
belong[now]=scc;
}
}
}
void rebuild()
{
cnt=0;
rep(x,1,n)
reg(x)
if(belong[x]!=belong[v])ed[++cnt]=(edge){belong[v],head2[belong[x]]},head2[belong[x]]=cnt,r[belong[v]]++;
}
void dp()
{
int head=0,tail=0;
rep(i,1,scc){
if(!r[i])q[tail++]=i;
f[i]=hav[i];g[i]=1;
}
while(head<tail){
int now=q[head++];
#define reg2(x) for(int i=head2[x];i;i=ed[i].next)
#define v2 ed[i].to
reg2(now){
r[v2]--;
if(!r[v2])q[tail++]=v2;
if(vis[v2]==now)continue;
if(f[now]+hav[v2]>f[v2]){
f[v2]=f[now]+hav[v2];
g[v2]=g[now];
}
else if(f[now]+hav[v2]==f[v2])g[v2]=(g[v2]+g[now])%mod;
vis[v2]=now;
}
}
}
int main()
{
n=read(),m=read(),mod=read();
rep(i,1,m){
int u=read(),V=read();
e[++cnt]=(edge){V,head[u]};head[u]=cnt;
}
rep(i,1,n)
if(!dfn[i])tarjan(i);
rebuild();
dp();
rep(i,1,scc){
if(f[i]>mx)mx=f[i],ans=g[i];
else if(f[i]==mx)ans=(ans+g[i])%mod;
}
cout<<mx<<endl<<ans<<endl;
return 0;
}
