首页 > 代码库 > 【BZOJ1093】【ZJOI2007】最大半联通子图 [拓扑][DP][Tarjan]

【BZOJ1093】【ZJOI2007】最大半联通子图 [拓扑][DP][Tarjan]

最大半连通子图

Time Limit: 30 Sec  Memory Limit: 162 MB
[Submit][Status][Discuss]

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)不会出现两次。

Output

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

Sample Input

  6 6 20070603
  1 2
  2 1
  1 3
  2 4
  5 6
  6 4

Sample Output

  3
  3

HINT

  N ≤100000, M ≤1000000;对于100%的数据, X ≤10^8

Main idea

  求最大半联通子图大小与个数。(最大半联通子图定义:在这个图内对于任意节点u,v,存在一条u->v的路径)

Source

  先跑一遍Tarjan,得到了两两连通的图,然后考虑如何加入单向连通的点集,显然两个强连通分量之间要是有连边的话,就可以满足这两个强连通分量的点单向连通,符合题意。

  那么答案显然就是在缩点后的DAG(有向无环图)上的最长路径

  用拓扑+DP(本质是在拓扑序上的DP)可以求出即为Ans,然后在跑的时候用一个数组f[i]统计一下相同的个数,注意更新dist的时候也要更新f,最后如果dist[i]=Ans,那么累加f[i],即为答案。

Code

技术分享
  1 #include<iostream>    2 #include<string>    3 #include<algorithm>    4 #include<cstdio>    5 #include<cstring>    6 #include<cstdlib>    7 #include<cmath>    8 using namespace std;    9     10 const int ONE=2000001; 11   12 int n,m,MOD; 13 int x,y; 14 int Next[ONE],First[ONE],Go[ONE],tot; 15 int next[ONE],first[ONE],go[ONE],Input[ONE]; 16 int dist[ONE]; 17 int T,t; 18 int tou,wei,jishu; 19 int q[ONE]; 20 int Ans,num,f[ONE]; 21 int Dfn[ONE],Low[ONE],vis[ONE],F[ONE],Num[ONE];  22   23 struct power 24 { 25         int u,v; 26 }a[ONE]; 27   28 int cmp(const power &a,const power &b) 29 { 30         if(a.u==b.u) return a.v<b.v; 31         return a.u<b.u; 32 } 33   34 int rule(const power &a,const power &b) 35 { 36         return (a.u==b.u && a.v==b.v);   37 } 38   39 int get()  40 {  41         int res,Q=1;    char c; 42         while( (c=getchar())<48 || c>57) 43         if(c==-)Q=-1; 44         if(Q) res=c-48;  45         while((c=getchar())>=48 && c<=57)  46         res=res*10+c-48;  47         return res*Q;  48 } 49   50 int Add(int u,int v) 51 { 52         Next[++tot]=First[u];   First[u]=tot;   Go[tot]=v; 53 } 54   55 int Add_edge(int u,int v) 56 { 57         next[++tot]=first[u];   first[u]=tot;   go[tot]=v;  Input[v]++; 58 } 59   60 void Tarjan(int u)  61 {  62         Dfn[u]=Low[u]=++T;  63         vis[u]=1;  64         q[++t]=u;  65         int v;  66         for(int e=First[u];e;e=Next[e])  67         {  68             int v=Go[e];  69             if(!Dfn[v])  70             {  71                 Tarjan(v);  72                 Low[u]=min(Low[u],Low[v]);    73             }     74             else    if(vis[v])  75             Low[u]=min(Low[u],Dfn[v]);  76         }  77               78         if(Low[u]==Dfn[u])  79         {  80             jishu++;  81             do 82             {  83                 v=q[t--];  84                 F[v]=jishu; 85                 vis[v]=0; 86                 Num[jishu]=Num[jishu]+1; 87              }while(v!=u);  88         } 89 } 90   91 void Rebuild() 92 { 93         num=0; 94         for(int u=1;u<=n;u++) 95         { 96             for(int e=First[u];e;e=Next[e]) 97             { 98                 int v=Go[e]; 99                 if(F[u]!=F[v])100                 {101                     a[++num].u=F[u];102                     a[num].v=F[v];103                 }104             }105         }106          107         sort(a+1,a+num+1,cmp);108         num=unique(a+1,a+num+1,rule)-1-a;109          110         for(int i=1;i<=num;i++)111         {112             Add_edge(a[i].u,a[i].v);113         }114 }115  116 void Topufirst()117 {118         for(int v=1;v<=jishu;v++)119         {120             if(!Input[v]) q[++wei]=v;121             dist[v]=Num[v];122             f[v]=1;123             Ans=max(Ans,dist[v]);124         }125 } 126  127 void TopuA()128 {129         while(tou<wei)130         {131             int u=q[++tou];132             for(int e=first[u];e;e=next[e])133             {134                 int v=go[e];135                 if(dist[v]<dist[u]+Num[v])136                 {137                     dist[v]=dist[u]+Num[v];138                     f[v]=f[u];139                     Ans=max(Ans,dist[v]);140                 }141                 else142                 if(dist[v]==dist[u]+Num[v]) f[v]=(f[v]+f[u])%MOD;143                 if(!(--Input[v])) q[++wei]=v;144             }145         }146 }147  148 int main()149 {      150         n=get();    m=get();    MOD=get();151         for(int i=1;i<=m;i++)152         {153             x=get();    y=get();154             Add(x,y);155         }156          157         for(int i=1;i<=n;i++)158         if(!Dfn[i]) Tarjan(i);159          160         tot=0;161         Rebuild();162          163         tou=0;  wei=0;164         Topufirst(); TopuA();165          166         tot=0;167         for(int i=1;i<=jishu;i++)168         if(dist[i]==Ans) tot=(tot+f[i])%MOD;169          170         printf("%d\n%d",Ans,tot);171 }
View Code

 

【BZOJ1093】【ZJOI2007】最大半联通子图 [拓扑][DP][Tarjan]