首页 > 其他分享 >图的连通性

图的连通性

时间:2024-02-10 12:44:04浏览次数:28  
标签:连通 遍历 连通性 点双 返祖 low 分量

图的连通性

这个专题,不太好说,因为涉及到的东西实在是太广泛太杂了,我们这里就只讲建模,至于建模之后的处理方式可以移步至其他的知识点。

强连通

对于有向图,我们可以发现,如果每个点的贡献和影响与这个点可达的点有关,那么我们就可以将一个强连通分量缩点,将原图转化为一个有向无环图,然后就可以套用 \(DAG\) 上的技巧进行处理。

然后就是,我们发现我们将这一个个强连通分量找出来的顺序恰好就是拓扑序的逆序,所以我们根本不需要建边,只需要根据需求正着或者倒着扫一遍即可。

点双联通

点双连通,一般来说都会有明显的提示,比如两个点路径的必经之点,又或者直接很明显的问你关于割点的问题。

求点双的方式和强连通类似,只不过,求点双是在遍历儿子的循环内部的,需要注意以下求割点的话要特判根,但是求点双不需要。

另外,两个点一条边的点双也是点双,这个玩意儿很容易弄错,这是点双中的骗徒,因为其他的点双都可以保证简单环,就双点点双这玩意儿,根本没有环!

顺带,说一下圆方树。

新建一些虚拟节点,称为方点,对于每一个点双都将点双内的所有点向方点连边,然后点双内部所有点互相的边断掉。

可以发现,任何两个点的路径一定是原点和方点交错出现的。

其次,任意两个点之间在原图上的必经点,就是他们在园方树上经过的所有圆点。

(这不比\(DFS\) 生成树好用多了)

边双联通

对于关于路径上必经边的题目,可以通过边双缩点,转化为一颗树,然后对树上问题进行处理。

另外就是,双连通没有横插边这种说法,所以可以放心大胆的丢掉 \(instack\) 这种东西。

小Trick

  1. 关于\(Tarjan\)基本原理

    正确性是怎么得到保证的呢,其实说白了就是用了这两条性质

    1. 若\(A\) 和 \(B\) 强连通,\(B\) 和 \(C\) 强连通,那么\(A\) 和 \(C\) 也强连通。
    2. 在\(DFS\) 树上,只要是被遍历了,就一定说明祖先到他的路径上的所有点都可以到达他,所以返祖边保证了和祖先的强连通,而\(low\) 数组相当于找的这个强连通分量目前的代言人。

    就这么简单,双连通的证明类似。

  2. 基于\(low\) 数组的\(Tarjan\) 扩展运用

    我们发现,我们同一个强连通分量里的点的\(low\) 值不一定相同,只是因为访问的先后顺序导致的。

    但是如果我们每次都先访问返祖边,然后再通过树枝边向下搜索,那么最后得到的\(low\) 数组对于同一个强连通分量一定是相同的,证明显然。

  3. 点双联通分量里的边

    众所周知,强连通和边双都非常好处理联通分量里的边,唯独点双这个玩意儿,因为一个点可能会存在于多个点双之中,而且还有可能一个点双里面的几个点对于全局来说都是割点的情况,所以说在算法外找边是非常麻烦的。

    所以我们可以直接在算法内解决,将记录点的栈改为记录边的栈即可,然后要注意,对于"返祖"的情况一定要认清楚究竟是返祖还是遍历了已遍历的子孙,记得特判这个。(找环的话要特别注意双点点双)

标签:连通,遍历,连通性,点双,返祖,low,分量
From: https://www.cnblogs.com/Ariginal/p/18012830

相关文章

  • 图论——连通性
    图论——连通性基本知识路径相关途径:连接一串结点的序列称为途径,用点序列\(v_{0..k}\)和边序列\(e_{1..k}\)描述,其中\(e_i=(v_{i-1},v_i)\),通常写为\(v_0\tov_1\to\cdots\tov_k\)。迹:不经过重复边的途径称为迹。回路:\(v_0=v_k\)的迹称为回路。......
  • 连通性问题
    求割点#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constllN=2e4+10;lln,m,dfn[N],low[N],tot,root;boolcut[N];vector<ll>G[N];voidtarjan(llu){ dfn[u]=low[u]=++tot; llflag=0; for(autov:G[u]){ if(!dfn[v]){ ta......
  • 网络连通性测试 【Connectivity】
    CFD简介CFD(ConnectivityFaultDetection,连通错误检测)是一种二层网络中的端到端OAM(Operation,Administration,andMaintenance,操作、管理和维护)技术,主要用于在二层网络中检测链路连通性,以及在故障发生时进行定位。适用的二层网络包括基于VLAN的以太网网络和基于MPLS的二层V**。......
  • 连通性容斥
    一种比较牛的东西,典型标志为\(n\le18\),计数满足特殊性质而且连通的状物。[ARC105F]有一张\(n\)个点\(m\)条边的简单无向图,问选出一个边集,使得\(n\)个点与这些边构成的图连通,并且图是二分图的方案数。\(1\leqn\leq17,n-1\leqm\leq\frac{n(n-1)}{2}\)。通用套路......
  • 自动化ping测网络连通性监测与Excel自动记录
    根据现有提供海量ip进行检测网络质量,如果手动操作那将成为一项很难完成的操作。为了简化这一任务,可以使用Python自动化脚本,利用openpyxl和pythonping库,自动执行ping测试并记录结果到Excel文件。openpyxl:openpyxl是一个用于操作Excel文件的库。它允许你读取、写入和......
  • WGCLOUD体验 - 监测数据库的连通性
    WGCLOUD是一款运维监测平台,可以监测服务器、主机、数据库、服务接口、网络设备等资源我是一名DBA,日常工作中,主要关注数据库方面的监测情况,正好WGCLOUD有一个模块可以检测数据库是否能连通,如果发现不能连通,会立刻发送告警通知(可以用邮件、钉钉、wx等方式)如下WGCLOUD不但可以检测数据......
  • 双连通性
    参考资料:虞皓翔《再谈图连通性相关算法》......
  • 连通性与 Tarjan
    强连通分量和Tarjan强连通分量(StronglyConnectedComponents,SCC),指的是极大的连通子图。tarjan算法,用于求图的强连通分量。dfs生成树有向图的dfs生成树大致分为四种边:树边(treeedge):示意图中以黑色边表示,每次搜索找到一个还没有访问过的结点的时候就形成了一条树边......
  • [学习笔记] Tarjan 连通性全家桶
    拜谢陈老师的PPT!!!无向图割点若点\(x\)不为搜索树的根节点,则\(x\)是割点当且仅当搜索树上存在一个\(x\)的子节点\(y\)满足:\(dfn_x\lelow_y\)。特别地,当\(x\)是搜索树的根节点时,则\(x\)是割点当且仅当有两个点\(y_1,y_2\)满足上述条件。割边边\((x,y)\)是......
  • 华为SAN存储在Red Hat系统下的主机连通性FAQ
    1、建立iSCSI连接后,主机系统无法重启现象主机系统和存储系统建立iSCSI连接后,主机系统重启失败。根因分析主机停止iSCSI服务时,session没有关掉。解决方案主机系统重启前,请先停止iSCSI服务,然后再重启主机。2、替换LUN后无法更新LUN的信息现象当替换LUN的时候(前后两个LUN使......