题解 P2272 【[ZJOI2007]最大半连通子图】

迈不过友情╰ 2021-11-29 06:42 186阅读 0赞

### [P2272 \[ZJOI2007\]最大半连通子图][P2272 _ZJOI2007] ###

萌新初学Tarjan，在《信息学奥赛一本通-提高篇》中看到这题，看到题解不多，便想发布一篇较为清新简洁的题解。——第5道紫题

题目大意：

定义最大半连通图：对于图中任意两点u，v,存在一条u到v的有向路径 **或者** 从v到u的有向路径。求一个图中不同的最大半连通子图的数目。

看到题面时大家很容易想到，如果两点互相可以到达，那么它们必是半连通图，所以考虑先Tarjan缩点（[P3387 【模板】缩点（Tarjan缩点+DAGdp）][P3387 _Tarjan_DAGdp]）

接着去除重边重新建图，你会发现，**在这个有向无环图（DAG）中，半连通子图都是一条链（可以举反例试试，这条链不可能有分支，否则将有两点无法抵达另一方）**

于是，G的最大半连通子图拥有的节点数K就是最长链长度，不同的最大半连通子图的数目就是最长链个数。

信息学一本通：最长链可以直接用拓扑排序（topo），最长链个数用一个类似DP的方法，用f【i】表示以 i 为终点的方案数，那么f【i】就等于满足距离为起点到 i 的临时最短距离的点的 f 的和。然后查找距离等于最长链的点，答案为它们的方案数之和

其他题解中已经给出了拓扑的算法，我借鉴大佬的程序用的是搜索，先一直搜到终点再回来更新答案。由于数据范围\#7一直RE，后来改为const int N=1e5+5,M=2e6+5;终于AC。。qwq高性能。。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+5,M=2e6+5; bool f[N]; //f 在搜索中判断是否走过 int n,m,mod,now,d[N],a[N],ans,maxans,ch[N]; //d指从u到终点的最长链距离，a指最长链点数，ch指出度 int h[N],u[M],v[M],r[N],nu[M],cnt; //h是链式前向星的建边head，u，v保存初始读入的边左右两点，nu存初始时边的编号，r是入度 int top,co,dfn[N],low[N],c[N],s[N],st[N]; //dfn，low，st用于Tarjan，c表所在强连通分量编号，s指所在强连通分量点数 struct edge { int h,to; } e[M]; #define rint register int #define min(a,b) (a<b? a:b) #define max(a,b) (a>b? a:b) inline bool cmp(int a,int b) { return u[a]<u[b] || (u[a]==u[b] && v[a]<v[b]); }//将边排序，方便重新建图 inline void add(int u,int v) { e[++cnt].h=h[u],h[u]=cnt,e[cnt].to=v; } inline int read() { int w=1,ans=0; char ch=getchar(); while(ch>'9'||ch<'0') if (ch=='-') w=-1,ch=getchar(); while(ch<='9'&& ch>='0') ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar(); return ans*w; } inline void Tarjan(int u) { dfn[u]=low[u]=++now; st[++top]=u; for (rint i=h[u]; i; i=e[i].h) { int v=e[i].to; if (!dfn[v]) Tarjan(v),low[u]=min(low[u],low[v]); else if (!c[v]) low[u]=min(low[u],dfn[v]); } if (low[u]==dfn[u]) { c[u]=++co,s[co]++; while(st[top]!=u) s[co]++,c[st[top]]=co,top--; top--; } }//标准缩点 inline void dfs(int u) { f[u]=1; if (!ch[u]) {//如果没有出度，即到头了 d[u]=s[u],a[u]=1;//距离为点数，以u为起点方案为1 maxans=max(maxans,d[u]);//更新最长链距离 return; } for (rint i=h[u]; i; i=e[i].h) { int v=e[i].to; if (!f[v]) dfs(v);//继续搜索链的后面 if (d[v]+s[u]>d[u])//若以u为起点的链距离可以更长 d[u]=d[v]+s[u],a[u]=a[v]%mod;//更新 else if (d[u]==d[v]+s[u])//若最长链距离相同 a[u]=(a[u]+a[v])%mod;//加上方案数 maxans=max(maxans,d[u]); } } int main() { n=read(),m=read(),mod=read(); for (rint i=1; i<=m; i++) u[i]=read(),v[i]=read(),add(u[i],v[i]); for (rint i=1; i<=n; i++) if (!dfn[i]) Tarjan(i); cnt=0; memset(h,0,sizeof h); memset(e,0,sizeof e); for (rint i=1; i<=m; i++) nu[i]=i,u[i]=c[u[i]],v[i]=c[v[i]]; sort(nu+1,nu+m+1,cmp);//按u，v排序边 for (rint i=1; i<=m; i++) { int num=nu[i]; if (u[num]!=v[num] && (u[num]!=u[nu[i-1]] || v[num]!=v[nu[i-1]]))//若此边不是自环，且与上一条边不同（去除重边） ++ch[u[num]],++r[v[num]],add(u[num],v[num]);} //出度入度加1，加边 for (rint i=1; i<=co; i++) if (!r[i] && !f[i]) dfs(i);//入度为0且未搜索过 for (rint i=1; i<=co; i++) if (d[i]==maxans) ans=(ans+a[i])%mod;//统计答案 printf("%d\n%d\n",maxans,ans); }

转载于:https://www.cnblogs.com/Randolph68706/p/11197172.html

[P2272 _ZJOI2007]: https://www.luogu.org/problemnew/show/P2272
[P3387 _Tarjan_DAGdp]: https://www.luogu.org/problemnew/show/P3387