本文共 3138 字，大约阅读时间需要 10 分钟。

Tarjan - ZJOI 2007 最大半连通子图 - 洛谷 P2272

一个有向图 G=(V,E) 称为半连通的 (Semi-Connected)，如果满足：∀u,v∈V，满足 u→v 或 v→u，即对于图中任意两点 u,v，存在一条 u 到 v 的有向路径或者从 v 到 u 的有向路径。

若 G′=(V′,E′) 满足，E′ 是 E 中所有和 V′ 有关的边，则称 G′ 是 G 的一个导出子图。

若 G′ 是 G 的导出子图，且 G′ 半连通，则称 G′ 为 G 的半连通子图。

若 G′ 是 G 所有半连通子图中包含节点数最多的，则称 G′ 是 G 的最大半连通子图。

给定一个有向图 G，请求出 G 的最大半连通子图拥有的节点数 K，以及不同的最大半连通子图的数目 C。

由于 C 可能比较大，仅要求输出 C 对 X 的余数。

输入格式

第一行包含三个整数 N,M,X。N,M 分别表示图 G 的点数与边数，X 的意义如上文所述；

接下来 M 行，每行两个正整数 a,b，表示一条有向边 (a,b)。

图中的每个点将编号为 1 到 N，保证输入中同一个 (a,b) 不会出现两次。

输出格式

应包含两行。

第一行包含一个整数 K，第二行包含整数 C mod X。

数据范围

$1\le N\le 10^5,1\le M\le 10^6,1\le X\le 10^8$

输入样例：

6 6 200706031 22 11 32 45 66 4

输出样例：

33

分析：

$由题意，强连通图也是半连通图，且强连通图中点的数量一定大于半连通图。$

$最大半连通子图等价于求一个强连通分量构成的最长链。$

$我们首先通过tarjan算法进行缩点，重新建立拓扑图。$

$接着我们在拓扑图上进行dp。$

$f[i]：已第i个强连通分量为终点的路径中，所有强连通分量中，点的数量之和的最大值。$

$g[i]：点的数量和的最大值为f[i]的不同方案总数。$

注意：

$本题强连通分量之间会有重边，为了避免遍历时重复计算，我们要对各连通分量之间的边去重。$

代码：

#include
   
    #include
    
     #include
     
      #include
      
       #define ll long longusing namespace std;const int N=100010, M=2000010;int n,m,mod;int h[N],hs[N],e[M],ne[M],idx;int stk[N],top;bool in_stk[N];int dfn[N],low[N],timestamp;int id[N],scc_cnt,Size[N];int f[N],g[N];void add(int h[],int a,int b){
       e[idx]=b,ne[idx]=h[a],h[a]=idx++;}void tarjan(int u){
       dfn[u]=low[u]=++timestamp;    stk[++top]=u,in_stk[u]=true;    for(int i=h[u];~i;i=ne[i])    {
           int j=e[i];        if(!dfn[j])        {
               tarjan(j);            low[u]=min(low[u],low[j]);        }        else if(in_stk[j]) low[u]=min(low[u],dfn[j]);    }        if(dfn[u]==low[u])    {
           ++scc_cnt;        int y;        do        {
               y=stk[top--];            in_stk[y]=false;            id[y]=scc_cnt;            Size[scc_cnt]++;        }while(y!=u);    }}void dp(){
       for(int i=scc_cnt;i;i--)    //tarjan算法过后 按照编号递减 已是拓扑序    {
           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]
       
         S;    //哈希函数 u*100000+v ,因为点的编号在1e5以内    for(int i=1;i<=n;i++)   //缩点后重新建图        for(int j=h[i];~j;j=ne[j])        {
               int k=e[j];            int u=id[i],v=id[k];            ll h=u*100000ll+v;            if(u!=v && !S.count(h))             {
                   add(hs,u,v);                S.insert(h);            }        }            dp();        int maxf=0,sum=0;    for(int i=1;i<=scc_cnt;i++)        if(maxf
       
      
     
    
   

转载地址：http://baor.baihongyu.com/