[tarjan缩点]「BZOJ1093」[ZJOI2007] 最大半连通子图-布布扣-bubuko.com

Description

　　一个有向图G=(V,E)称为半连通的(Semi-Connected)，如果满足：?u,v∈V，满足u→v或v→u，即对于图中任意
两点u，v,存在一条u到v的有向路径或者从v到u的有向路径。若G‘=(V‘,E‘)满足V‘?V，E‘是E中所有跟V‘有关的边，
则称G‘是G的一个导出子图。若G‘是G的导出子图，且G‘半连通，则称G‘为G的半连通子图。若G‘是G所有半连通子图
中包含节点数最多的，则称G‘是G的最大半连通子图。给定一个有向图G，请求出G的最大半连通子图拥有的节点数K
，以及不同的最大半连通子图的数目C。由于C可能比较大，仅要求输出C对X的余数。

Input

　　第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述接下来M行，每行两个正整
数a, b，表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。N ≤1
00000, M ≤1000000；对于100%的数据， X ≤10^8

Output

　　应包含两行，第一行包含一个整数K。第二行包含整数C Mod X.

题解

tarjan缩点，DAG上DP

注意缩点之后的图可能有重边要特判掉

用记忆化搜索有很多细节要注意

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100000+15,M=1000000+15;
int n,m,mod;

struct tu{int num,last[N],nxt[M],ver[M];
          inline void add(int x,int y) {nxt[++num]=last[x]; last[x]=num; ver[num]=y;}
         }g,sc;

int t,pre[N],low[N],  scnt,scc[N],v[N],f[N],  top,s[N];
void dfs(int x)
 { pre[x]=low[x]=++t;  s[++top]=x;
  
   for(int i=g.last[x];i;i=g.nxt[i])
     { int y=g.ver[i];
     
       if(!pre[y]) {dfs(y);   low[x]=min(low[x],low[y]); } 
       
       else if(!scc[y]) low[x]=min(low[x],pre[y]);  
     }
   
   if(low[x]==pre[x])
    {scnt++;
    
     while(1)
      {scc[s[top]]=scnt;  f[scnt]=++v[scnt];
       if(s[top--]==x) break;
	  }
	}  
 }
int ans,c,cnt[N],tim[N]; bool vis[N];

void solve(int x)
 {vis[x]=1; cnt[x]=1;
 
  for(int i=sc.last[x];i;i=sc.nxt[i])
   { int y=sc.ver[i]; 
   if(tim[y]==x) continue;
   tim[y]=x; //
   if(!vis[y])   solve(y);
   
    if(f[y]+v[x]>f[x]) f[x]=f[y]+v[x],cnt[x]=cnt[y]%mod;
    else if(f[y]+v[x]==f[x]) cnt[x]=(cnt[x]+cnt[y])%mod;
    
   }	
 }
int main()
 {
 scanf("%d%d%d",&n,&m,&mod); int x,y;
 	
 while(m--)	{scanf("%d%d",&x,&y); g.add(x,y); }
 	
 for(int i=1;i<=n;i++) if(!pre[i]) dfs(i); 	
 	
 for(int x=1;x<=n;x++) 
  for(int j=g.last[x];j;j=g.nxt[j])	
   {y=g.ver[j];
    if(scc[x]!=scc[y]) sc.add(scc[x],scc[y]);
   }
 	
 for(int i=1;i<=scnt;i++) {if(!vis[i]) solve(i); 
                           if(f[i]>ans)       ans=f[i],c=cnt[i]%mod;
                           else if(f[i]==ans) c=(c+cnt[i])%mod; 
 	                      }
 printf("%d\n%d",ans,c);	
 	
return 0; 	
 }

[tarjan缩点]「BZOJ1093」[ZJOI2007] 最大半连通子图

原文：https://www.cnblogs.com/YuXiaoze/p/11250566.html