最大半联通子图
思路：
先缩点，然后去除重边，重新建图，再跑一个拓扑，过程中DP记录强连通分量 i 的大小 f [ i ]
g [ i ]表示同等于第 i 个强连通分量的最大同大小图个数
#include<bits/stdc++.h>
using namespace std;
int dfn[100005],low[100005],top=0,xxx,num[100005],size[100005],dis[100005],cnt;
vector<int> a[100005],p[100005];
vector<pair<int,int>> c;
int y[100005],res,vis[100005],f[100005],g[100005],b[100005],st[100005];
queue<int> t;
stack<int> q;
void tarjan(int x){
dfn[x]=low[x]=++top;
vis[x]=1;
q.push(x);
for(auto i:a[x]){
int v=i;
if(!dfn[v]){
tarjan(v);
low[x]=min(low[x],low[v]);
}else if(vis[v]&&dfn[v]<low[x]){//返祖边
low[x]=dfn[v];
}
}
if(dfn[x]==low[x]){
cnt++;
size[cnt]=0;
while(q.top()!=x){
vis[q.top()]=0;
b[q.top()]=cnt;
q.pop();
size[cnt]++;
}
vis[x]=0;
b[x]=cnt;
size[cnt]++;
q.pop();
}
}
int n,m;
int main(){
scanf("%d%d%d",&n,&m,&xxx);
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
a[u].push_back(v);
}
memset(low,0x3f,sizeof(low));
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i);
}
}
//build
for(int i=1;i<=n;i++){
for(auto v:a[i]){//遍历有关a[i]的点
if(b[i]!=b[v]){//不在同一强连通分量
c.push_back({b[i],b[v]});
}
}
}
sort(c.begin(),c.end());
int ii=0;
for(auto e:c){
int u=e.first,v=e.second;
//去重
if(ii>0&&c[ii-1].first==u&&c[ii-1].second==v){
ii++;
continue;
}
p[u].push_back(v);//新图
dis[v]++;
ii++;
}
//
//solve
for(int j=1;j<=cnt;j++){
if(dis[j]==0){
t.push(j);
}
f[j]=size[j];
g[j]=1;
}
while(!t.empty()){
auto x=t.front();
t.pop();
for(auto v:p[x]){
dis[v]--;
if(f[x]+size[v]==f[v]){
g[v]=(g[x]+g[v])%xxx;
}
else if(f[x]+size[v]>f[v]){
g[v]=g[x];
f[v]=f[x]+size[v];
}
if(dis[v]==0){
q.push(v);
}
}
}
//
// int ans=0;
// for(int i=1;i<=cnt;i++){
// ans=max(ans,f[i]);
// }
int pos=0,kkk=0;
for(int i=1;i<=cnt;i++){
if(f[i]>f[pos]){
pos=i;
kkk=g[pos];
}else if(f[i]==f[pos]) kkk=(kkk+g[i])%xxx;
}
printf("%d\n%d",f[pos],kkk);
return 0;
}