最大半连通子图

解题思路：只要找一个最长的链，因为不需要两个点互相到达，只需要一个点能到另一个点就行了，但是这条链不能分叉，先tarjan，缩点，建新图，然后用递推思想，从ssc_cnt开始递减，按照拓扑序做，g[]数组代表以i点为终点的方案数，f[]数组代表以i为终点集合中点的数量。如果f[k]<f[i]+size[k]
g[k]=g[i],更新f[k]，如果相等g方案数相加就行了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
using namespace std;
const int N=100010,M=2000010;
int h[N],hs[N],e[M],idx,ne[M];
int ssc_cnt,Size[N],id[N];
int dfn[N],low[N];
int f[N],g[N];
int n,m,mod;
int s[N];
bool is[N];
int top,timestamp;
set<long long>ss;
void add(int h[],int a,int b)
{
   
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void targan(int u)
{
   
    low[u]=dfn[u]=++timestamp;
    s[++top]=u,is[u]=true;
    for(int i=h[u];~i;i=ne[i])
    {
   
        int j=e[i];
        if(!dfn[j])
        {
   
            targan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(is[j])
        {
   
            low[u]=min(low[u],dfn[j]);
        }
    }
    if(low[u]==dfn[u])
    {
   
        int y;
        ++ssc_cnt;
        do{
   
            y=s[top--];
            is[y]=false;
            Size[ssc_cnt]++;
            id[y]=ssc_cnt;
        }while(y!=u);
    }
}
int main()
{
   
    memset(h,-1,sizeof h);
    memset(hs,-1,sizeof hs);
    scanf("%d%d%d",&n,&m,&mod);
    while(m--)
    {
   
        int a,b;
        cin>>a>>b;
        add(h,a,b);
    }
    for(int i=1;i<=n;i++)
    if(!dfn[i])
    targan(i);
    for(int i=1;i<=n;i++)
    {
   
    for(int j=h[i];~j;j=ne[j])
    {
   
        int k=e[j];
        long long hash=id[i]*1000000ll+id[k];
        if(id[k]!=id[i]&&!ss.count(hash))
        {
   
            ss.insert(hash);
            add(hs,id[i],id[k]);
        }
    }
    }
    long long sum=0;
    int maxv=0;
    for(int i=ssc_cnt;i;i--)
   {
   
       if(!f[i])
       f[i]=Size[i],g[i]=1;
    for(int j=hs[i];~j;j=ne[j])
    {
   
        int k=e[j];
        if(f[k]<f[i]+Size[k])
        {
   
            g[k]=g[i];
            f[k]=f[i]+Size[k];
        }
        else if(f[k]==f[i]+Size[k])
        {
   
            g[k]=(g[k]+g[i])%mod;
        }
    }
   }
    for(int i=1;i<=ssc_cnt;i++)
    {
   
        if(f[i]>maxv)
        {
   
            maxv=f[i];
            sum=g[i];
        }
        else if(f[i]==maxv)
        {
   
            sum=(sum+g[i])%mod;
        }
    }
    cout<<maxv<<endl;
    cout<<sum<<endl;
    return 0;
}