思路

半连通导出子图在缩点DAG上对应带SCC大小的路径，求最大权和与路径数；不同原边收缩成同一边必须去重，避免把相同顶点集重复计数；10万点百万边迭代DFS防栈溢出。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
vector<int>components(const vector<vector<int>>&g,const vector<vector<int>>&rev,int &count){int n=g.size();vector<int>seen(n),order,next(n);for(int s=0;s<n;s++)if(!seen[s]){vector<int>st(1,s);seen[s]=1;while(!st.empty()){int u=st.back();if(next[u]<(int)g[u].size()){int v=g[u][next[u]++];if(!seen[v]){seen[v]=1;st.push_back(v);}}else{order.push_back(u);st.pop_back();}}}vector<int>c(n,-1);count=0;for(auto it=order.rbegin();it!=order.rend();++it)if(c[*it]<0){vector<int>st(1,*it);c[*it]=count;while(!st.empty()){int u=st.back();st.pop_back();for(int v:rev[u])if(c[v]<0){c[v]=count;st.push_back(v);}}count++;}return c;}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m,mod;cin>>n>>m>>mod;vector<vector<int>>g(n),rev(n);vector<pair<int,int>>edges;edges.reserve(m);while(m--){int u,v;cin>>u>>v;--u;--v;g[u].push_back(v);rev[v].push_back(u);edges.push_back({u,v});}int count;auto c=components(g,rev,count);vector<vector<int>>dag(count);vector<int>sz(count),degree(count);for(int v:c)sz[v]++;for(auto e:edges)if(c[e.first]!=c[e.second])dag[c[e.first]].push_back(c[e.second]);for(auto &a:dag){sort(a.begin(),a.end());a.erase(unique(a.begin(),a.end()),a.end());for(int v:a)degree[v]++;}vector<int>d=sz,ways(count,1%mod);queue<int>q;for(int i=0;i<count;i++)if(!degree[i])q.push(i);while(!q.empty()){int u=q.front();q.pop();for(int v:dag[u]){int value=d[u]+sz[v];if(value>d[v]){d[v]=value;ways[v]=ways[u];}else if(value==d[v])ways[v]=(ways[v]+ways[u])%mod;if(--degree[v]==0)q.push(v);}}int best=*max_element(d.begin(),d.end()),ans=0;for(int i=0;i<count;i++)if(d[i]==best)ans=(ans+ways[i])%mod;cout<<best<<'\n'<<ans<<'\n';}