题面
一句话题意：若一个图，取出一个子图，子图中任两点u，v，总有u—>v 或 v—>u，且子图节点数最多，则称为最大半连通子图，求最大半连通子图节点数和个数。
思路
先tarjin缩点，注意顺便求出每个强连通分量中的节点个数。
void tarjin(int k)
{
low[k]=dfn[k]=++cntt,st.push(k);
for(int i=head[k]; i; i=a[i].nxt)
if(!dfn[a[i].to]) tarjin(a[i].to),low[k]=min(low[k],low[a[i].to]);
else if(!co[a[i].to]) low[k]=min(low[k],dfn[a[i].to]);
if(low[k]==dfn[k])
{
co[k]=++num,tot[num]++;
while(st.top()!=k) co[st.top()]=num,tot[num]++,st.pop();
st.pop();
}
}//tarjin合点
（两个tot[num]++即计算节点个数）
其次，重新建树，把一个强连通分量视作一个点，注意不要重边。
void rebuild()
{
for(int i=1; i<=m; i++) a[i].x=co[a[i].x],a[i].y=co[a[i].y];
sort(a+1,a+m+1,cmp),cnt=0,memset(head,0,sizeof(head));
for(int i=1; i<=m; i++)
if((a[i].x!=a[i].y)&&(a[i].x!=a[i+1].x||a[i].y!=a[i+1].y))
add(a[i].x,a[i].y),in[a[i].y]++;
}//重新建树
其中，cmp函数按强连通分量编号排序
bool cmp(node w,node v)
{
if(w.x!=v.x) return w.x<v.x;
return w.y<v.y;
}
排序完后，只要前后两条边两个端点编号不同，即为不同的边。并且，一条边两个端点不能相同（即无自环）。这就是这个if语句的意思。
if((a[i].x!=a[i].y)&&(a[i].x!=a[i+1].x||a[i].y!=a[i+1].y))
再然后，这道题的最大半连通子图即求“最长链”（因为图中已经无环了），但不完全是（具体见代码），答案的第一行即为各个链，每个链的强连通分量（中）节点数之和，的最大值。
如何求这个最大值？我们可以用dp/递推，用dis[i]表示以第i个强连通分量结尾的链中，最多的节点数。那么就有状态转移方程了
if(dis[a[i].to]<dis[k]+tot[a[i].to]) //最长距离被更新
dis[a[i].to]=dis[k]+tot[a[i].to];
至于总个数，我们可以用s数组记录，s[i]即第i个强连通分量结尾的“最长链”的个数。则，s[i]=(s[i]+s[k])%mod，这里k是有边到强连通分量i的，且dis[k]=dis[i]-tot[i]的强连通分量。（注，这里最大长度dis[i]被更新后，s[i]应该清零）。
if(dis[a[i].to]==dis[k]+tot[a[i].to]) s[a[i].to]=(s[a[i].to]+s[k])%mod;
下面给出整个拓扑排序的代码。
void tuopu() //拓扑排序求最长链,dp
{
for(int i=1; i<=num; i++)
if(!in[i])
q.push(i),s[i]=1,dis[i]=tot[i],ans=(dis[ans]<dis[i])?i:ans;
while(!q.empty())
{
int k=q.front();
q.pop();
for(int i=head[k]; i; i=a[i].nxt)
{
--in[a[i].to];
if(dis[a[i].to]<dis[k]+tot[a[i].to]) //最长距离被更新
dis[a[i].to]=dis[k]+tot[a[i].to],s[a[i].to]=0,ans=(dis[ans]<dis[a[i].to])?a[i].to:ans;
if(dis[a[i].to]==dis[k]+tot[a[i].to]) s[a[i].to]=(s[a[i].to]+s[k])%mod;
if(!in[a[i].to]) q.push(a[i].to);
}
}
}
这里的ans是为了记录最长链的长度而设的，dis[ans]即最大的长度。
拓扑排序完了后，就可以统计第二个答案（总个数）了，总个数就是dis[i]为max的几个强连通分量的s[i]的和。
void getans() //累计求答案
{
for(int i=1; i<=n; i++)
if(dis[i]==dis[ans]) ansn=(ansn+s[i])%mod;
}
ansn是统计的总个数的，别忘了"%mod"。
最后我们就得到了两个答案，dis[ans]和ansn。
代码
#include <bits/stdc++.h>
using namespace std;
int n,m,ansn,ans,mod,x,y;
int head[100005],cnt,dis[100005],in[100005],s[100005];
int dfn[100005],co[100005],low[100005],tot[100005],num,cntt;
struct node
{
int nxt,to,x,y;
} a[1000005];
stack<int> st;
queue<int> q;
void add(int x,int y)
{
a[++cnt].nxt=head[x],a[cnt].to=y,a[cnt].x=x,a[cnt].y=y,head[x]=cnt;
}
void tarjin(int k)
{
low[k]=dfn[k]=++cntt,st.push(k);
for(int i=head[k]; i; i=a[i].nxt)
if(!dfn[a[i].to]) tarjin(a[i].to),low[k]=min(low[k],low[a[i].to]);
else if(!co[a[i].to]) low[k]=min(low[k],dfn[a[i].to]);
if(low[k]==dfn[k])
{
co[k]=++num,tot[num]++;
while(st.top()!=k) co[st.top()]=num,tot[num]++,st.pop();
st.pop();
}
}//tarjin合点
bool cmp(node w,node v)
{
if(w.x!=v.x) return w.x<v.x;
return w.y<v.y;
}
void rebuild()
{
for(int i=1; i<=m; i++) a[i].x=co[a[i].x],a[i].y=co[a[i].y];
sort(a+1,a+m+1,cmp),cnt=0,memset(head,0,sizeof(head));
for(int i=1; i<=m; i++)
if((a[i].x!=a[i].y)&&(a[i].x!=a[i+1].x||a[i].y!=a[i+1].y))
add(a[i].x,a[i].y),in[a[i].y]++;
}//重新建树
void tuopu() //拓扑排序求最长链,dp
{
for(int i=1; i<=num; i++)
if(!in[i])
q.push(i),s[i]=1,dis[i]=tot[i],ans=(dis[ans]<dis[i])?i:ans;
while(!q.empty())
{
int k=q.front();
q.pop();
for(int i=head[k]; i; i=a[i].nxt)
{
--in[a[i].to];
if(dis[a[i].to]<dis[k]+tot[a[i].to]) //最长距离被更新
dis[a[i].to]=dis[k]+tot[a[i].to],s[a[i].to]=0,ans=(dis[ans]<dis[a[i].to])?a[i].to:ans;
if(dis[a[i].to]==dis[k]+tot[a[i].to]) s[a[i].to]=(s[a[i].to]+s[k])%mod;
if(!in[a[i].to]) q.push(a[i].to);
}
}
}
void getans() //累计求答案
{
for(int i=1; i<=n; i++)
if(dis[i]==dis[ans]) ansn=(ansn+s[i])%mod;
}
int main()
{
scanf("%d%d%d",&n,&m,&mod);
for(int i=1; i<=m; i++) scanf("%d%d",&x,&y),add(x,y);
for(int i=1; i<=n; i++) if(!dfn[i]) tarjin(i);
rebuild(),tuopu(),getans();
printf("%d\n%d\n",dis[ans],ansn);
return 0;
}
这个代码没加多少注释，因为前面讲的够详细了（不懂请先看前面，或者私信我）。
小结
首先是思路，我是参考了一本通的书的，那本书上讲的也是比较清楚了，我在加两句解释一下，希望对你有帮助。
其次是一个老问题，我老是把i和j搞混，好很难调，请务必小心。
最后是老生常谈的码风问题，有点丑，有点压行，请见谅。
完结撒花！
别忘了给赞，关注啊。
