题目描述
一个有向图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的余数。
输入格式
第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述接下来M行，每行两个正整数a, b，表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。
输出格式
应包含两行，第一行包含一个整数K。第二行包含整数C Mod X.
说明/提示
对于100%的数据，N<=100000, M<=1000000, X<=1e8
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int mod;
const int N=2e5+10,M=2e6+10;
int next[M],head[N],go[M],tot;
inline void add(int u,int v){
next[++tot]=head[u];head[u]=tot;go[tot]=v;
}
int dfn[N],low[N],co[N],st[N],sz[N],top,num,col;
inline void Tarjan(int u){
dfn[u]=low[u]=++num;
st[++top]=u;
for(int i=head[u];i;i=next[i]){
int v=go[i];
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}else if(!co[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
co[u]=++col;
sz[col]=1;
while(st[top]!=u){
co[st[top]]=col;
sz[col]++;
--top;
}
--top;
}
}
struct E{
int u,v;
}e[M];
int in[N];
int n,m;
struct node{
int u,dat;
};
int dis[N],dp[N];
inline void topsort(){
queue<int>q;
for(int i=1;i<=col;i++){
if(!in[i])q.push(i);
dis[i]=sz[i],dp[i]=1;
}
while(q.size()){
int u=q.front();q.pop();
for(register int i=head[u];i;i=next[i]){
int v=go[i];
if(dis[v]<dis[u]+sz[v]){
dis[v]=dis[u]+sz[v];
dp[v]=dp[u];
}else if(dis[v]==dis[u]+sz[v]){
dp[v]=(dp[v]+dp[u])%mod;
}
--in[v];
if(in[v]==0)q.push(v);
}
}
int ans1=0,ans2=0;
for(int i=1;i<=col;i++){
if(dis[i]==ans1)
ans2=(ans2+dp[i])%mod;
if(dis[i]>ans1)
ans1=dis[i],ans2=dp[i];
}
cout<<ans1<<endl<<ans2;
}
bool cmp(E t1,E t2){
if(co[t1.u]==co[t2.u])return co[t1.v]<co[t2.v];
else return co[t1.u]<co[t2.u];
}
signed main(){
cin>>n>>m>>mod;
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
e[i]=(E){u,v};
add(u,v);
}
for(int i=1;i<=n;i++)
if(!dfn[i])Tarjan(i);
memset(next,0,sizeof(next));
memset(head,0,sizeof(head));
memset(go,0,sizeof(go)),tot=0;
sort(e+1,e+1+m,cmp);
for(int i=1;i<=m;i++){
if(co[e[i].u]==co[e[i-1].u]&&co[e[i].v]==co[e[i-1].v])continue;
if(co[e[i].u]!=co[e[i].v])
add(co[e[i].u],co[e[i].v]),in[co[e[i].v]]++;
}
topsort();
}