Tarjan水题系列(5):最大半连通子图 [ZJOI2007 luogu P2272]

大意：
缩点后转为求最长链的长度和最长链的个数
思路:
看懂题就会做系列长度和个数都可以拓扑排序后DP求得毕竟是2007年的题
代码:
如下
 #include <cstdio>

 #include <iostream>

 #include <memory.h>

 #define r(x) x=read()

 #define MAXX 100005

 #define MIN(a,b) (a<b?a:b)

 #define MAX(a,b) (a>b?a:b)

 #define re register

 using namespace std;

 typedef long long ll;

 int read()

 {

   char ch=;int w=;

   while(ch<''||ch>''){ch=getchar();}

   while(ch>=''&&ch<=''){w=w*+ch-'';ch=getchar();}

   return w;

 }

 int low[MAXX],dfn[MAXX],k,id[MAXX],num,top,sta[MAXX],du[MAXX];

 int h2[MAXX],h[MAXX],u,to,cnt,book[MAXX],heap,sta2[MAXX];

 int X,dp[MAXX],ans,w[MAXX],ans2[MAXX];

 int n,m;

 struct edge{int to,nex;}e[MAXX<<],e2[MAXX<<];

 void add(int u,int to,int x)

 {

   cnt++;

   if(x==) {e2[cnt]=(edge){to,h2[u]};h2[u]=cnt;}

   if(x==) {e[cnt]=(edge){to,h[u]};h[u]=cnt;}

 }

 void tarjan(int now)

 {

   low[now]=dfn[now]=++k;

   sta[++top]=now;

   for(int i=h2[now];i;i=e2[i].nex)

   {

     if(!dfn[e2[i].to])

       tarjan(e2[i].to),low[now]=MIN(low[now],low[e2[i].to]);

     else

       if(!id[e2[i].to])

         low[now]=MIN(low[now],dfn[e2[i].to]);

   }

   if(dfn[now]==low[now])

   {

     id[now]=++num;

     while(sta[top]!=now){id[sta[top]]=num;--top;}

     top--;

   }

 }

 int main()

 {

   r(n),r(m),r(X);

   for(re int i=;i<=m;++i)

     r(u),r(to),add(u,to,);

   for(re int i=;i<=n;++i)

     if(!dfn[i])

       tarjan(i);

   for(re int i=;i<=n;++i)

     w[id[i]]++;

   cnt=;

   for(re int i=;i<=n;++i)

     for(re int j=h2[i];j;j=e2[j].nex)

     {

       int y=id[e2[j].to],x=id[i];

       if(x!=y) add(x,y,),du[y]++;

     }

   for(re int i=;i<=num;++i)

     if(!du[i]) sta[++top]=i,dp[i]=w[i],ans2[i]=;

   for(re int i=;i<=top;++i)

   {

     int x=sta[i];

     for(re int j=h[x];j;j=e[j].nex)

     {

       du[e[j].to]--;

       if(du[e[j].to]==) sta[++top]=e[j].to;

       if(book[e[j].to]) continue;

       book[e[j].to]=,sta2[++heap]=e[j].to;

       if(dp[e[j].to]<dp[x]+w[e[j].to])

         dp[e[j].to]=dp[x]+w[e[j].to],ans2[e[j].to]=;

       if(dp[e[j].to]==dp[x]+w[e[j].to])

         ans2[e[j].to]=(ans2[e[j].to]+ans2[x])%X;

     }

     while(heap){book[sta2[heap]]=;heap--;}

     ans=MAX(ans,dp[x]);

   }

   ll anse=;

   for(int i=;i<=num;++i)

     if(dp[i]==ans) anse=(anse+ans2[i])%X;

   printf("%d\n%lld",ans,anse);

   return ;

 }