P2272 最大半连通子图

题解：对于每个强连通分量一定是半连通子图，对于每条线上的所有强连通的分量的所有点而言也是半连通子图。因此只需要先缩点记录每个强连通分量的大小，然后倒序（拓扑图）在新图跑最长路+计数即可。

  1 #include<bits/stdc++.h>
  2 #define ll long long
  3 using namespace std;
  4 const int N=1e5+100,M=2e6+100;
  5 int h[N],hs[N],e[M],ne[M],idx;
  6 int f[N],cnt[N],isz[N];
  7 int id[N],scc_cnt;
  8 stack<int>stk;
  9 bool is_stk[N];
 10 int dfn[N],low[N];
 11 int n,m,mod;
 12 unordered_set<ll>S;
 13 int times;
 14 int siz[N];
 15 void add(int h[],int a,int b)
 16 {
 17     ne[idx]=h[a],e[idx]=b,h[a]=idx++;
 18 }
 19 void tarjin(int u)
 20 {
 21     stk.push(u);
 22     low[u]=dfn[u]=++times;
 23     is_stk[u]=true;
 24     for(int i=h[u];i!=-1;i=ne[i])
 25     {
 26         int j=e[i];
 27         if(!dfn[j])
 28         {
 29             tarjin(j);
 30             low[u]=min(low[u],low[j]);
 31         }
 32         else if(is_stk[j]) low[u]=min(low[u],low[j]);
 33     }
 34     if(low[u]==dfn[u])
 35     {
 36         int y;
 37         ++scc_cnt;
 38         while(y!=u)
 39         {
 40             y=stk.top();
 41             stk.pop();
 42             is_stk[y]=false;
 43             siz[scc_cnt]++;
 44             id[y]=scc_cnt;
 45         }
 46     }
 47 }
 48 int main()
 49 {
 50     memset(h,-1,sizeof h);
 51     memset(hs,-1,sizeof hs);
 52     cin>>n>>m>>mod;
 53     while(m--)
 54     {
 55         int a,b;
 56         scanf("%d%d",&a,&b);
 57         add(h,a,b);
 58     }
 59     for(int i=1;i<=n;i++)
 60     if(!dfn[i])
 61     tarjin(i);
 62     for(int i=1;i<=n;i++)
 63     for(int j=h[i];j!=-1;j=ne[j])
 64     {
 65         int k=e[j];
 66         int a=id[i],b=id[k];
 67         ll Hash=a*1000000ll+b;
 68         if(a!=b&&S.count(Hash))
 69         {
 70             add(hs,a,b);
 71             S.insert(Hash);
 72         }
 73     }
 74     for(int i=scc_cnt;i;i--)
 75     {
 76         if(!f[i])
 77         {
 78             f[i]=siz[i];
 79             cnt[i]=1;
 80         }
 81         for(int j=hs[i];j!=-1;j=ne[j])
 82         {
 83             int k=e[j];
 84             if(f[k]<f[i]+siz[k])
 85             {
 86                 f[k]=f[i]+siz[k];
 87                 cnt[k]=cnt[i];
 88             }
 89             else if(f[k]==f[i]+siz[k])
 90             {
 91                 cnt[k]=((ll)cnt[k]+cnt[i])%mod;
 92             }
 93         }
 94     }
 95         ll maxf=0,sum=0;
 96         for(int i=1;i<=scc_cnt;i++)
 97         {
 98             if(f[i]>maxf)
 99             {
100                 maxf=f[i];
101                 sum=cnt[i];
102             }
103             else if(f[i]==maxf)
104             {
105                 sum=(sum+cnt[i])%mod;
106             }
107         }
108         printf("%lld
%lld
",maxf,sum%mod);
109     return 0;
110 }