wordpress 图片站模板,抖音seo工具,写文章一篇30元兼职,公司查询网全国企业信息查询官网概念
割边#xff08;Bridge 或 Cut Edge#xff09;
定义#xff1a;
在一个无向连通图中#xff0c;如果删除某条边后#xff0c;图不再连通#xff08;即任意两点之间不能相互到达#xff09;#xff0c;则称该边为割边。割边也被称为桥#xff0c;因为它像桥梁…概念
割边Bridge 或 Cut Edge
定义
在一个无向连通图中如果删除某条边后图不再连通即任意两点之间不能相互到达则称该边为割边。割边也被称为桥因为它像桥梁一样连接着图的两部分一旦移除这两部分就被隔断了。
特性
割边只存在于无向连通图中。删除割边会导致图的连通分量数量增加。割边是图中的一个“薄弱环节”对于图的连通性有重要影响。
边双连通分量Edge Biconnected Component
定义 一个无向图的边双连通分量是一个极大连通子图删除任意一条边后图仍然连通。类似于点双连通分量边双连通分量中的任意两个节点之间都有两条不相交的边即如果删除一条边仍然可以保持连通。 性质 边双连通分量的每个分量都是连通的。边双连通分量可用于分析图中冗余的边以及提高图的可靠性。
割点Articulation Point 或 Cut Vertex
定义
在一个无向连通图中如果删除了某个顶点后图不再连通即任意两点之间不能相互到达则称该顶点为割点。割点也被称为关节点因为它像关节一样连接着图的不同部分一旦移除这些部分就被分开了。
特性
割点同样只存在于无向连通图中。删除割点会导致图的连通分量数量增加或减少具体取决于割点的位置和图的结构。割点是图中的一个重要节点对于维护图的连通性至关重要。
点双连通分量Vertex Biconnected Component 定义 一个无向图的点双连通分量是一个极大连通子图删除任意一个节点后图仍然连通。换句话说点双连通分量中的任意两个节点之间都有两条不相交的路径即如果删除一个节点仍然可以保持连通。 性质 点双连通分量的每个分量都是连通的。点双连通分量可用来检测图中的割点即删除后会增加连通分量的节点。
割点与割边的关系 存在割点时必有割边如果一个节点是割点那么至少存在一条通过该节点的割边。删除割点会导致图分裂为多个部分每个部分之间至少存在一条割边。 割边连接的节点可能是割点割边的两个端点节点至少有一个可能是割点。特别是在边的两个端点是不同的双连通分量时这两个节点通常是割点。 独立的关系虽然割点和割边紧密相关但它们也可以独立存在。一个图可以有割点而没有割边或者有割边而没有割点。例如星型图的中心节点是割点但星型图的每条边都是割边。
Tarjan算法
算法思想
DFS 访问顺序 每个节点都有一个 dfn 值表示节点在 DFS 中被访问的时间戳第几个被访问。同时还有一个 low 值表示节点能通过回边或子节点到达的最早访问的节点的时间戳。割点判定 对于根节点如果它有两个或两个以上的子树则它是割点。对于非根节点如果某个子节点的 low 值不小于该节点的 dfn 值则该节点是割点。 割边判定 如果某个节点 u 和它的子节点 v 之间的边满足 low[v] dfn[u]则边 (u, v) 是割边。
算法步骤
初始化 dfn 和 low 数组初始值为 -1表示未被访问。初始化一个时间戳变量 time 为 0。使用 DFS 遍历图对于每个未被访问的节点调用 DFS 函数。在 DFS 函数中 设置当前节点的 dfn 和 low 值为当前时间戳并将时间戳加 1。对于每个邻接节点如果该邻接节点未被访问递归调用 DFS 函数更新当前节点的 low 值。如果邻接节点已被访问且不是父节点更新当前节点的 low 值为邻接节点的 dfn 值。在返回时根据 low 值判断是否是割点或割边。 记录所有割点和割边。
算法模板
// 求解割点的函数
vectorint findCutPoints(const vectorvectorint graph) {int n graph.size();vectorint cutPoints; // 存储割点vectorint dfn(n, -1), low(n), parent(n, -1); // 初始化 dfn, low, parent 数组vectorbool visited(n, false); // 记录节点是否已被访问int time 0; // 时间戳// DFS 函数functionvoid(int) dfs [](int u) {visited[u] true; // 标记节点 u 为已访问dfn[u] low[u] time; // 设置 dfn 和 low 值int childCount 0; // 子节点数量bool isCutPoint false; // 是否为割点// 遍历邻接节点for (int v : graph[u]) {if (!visited[v]) { // 如果 v 未被访问parent[v] u; // 设置 v 的父节点为 udfs(v); // 递归调用 DFSchildCount; // 增加子节点数量// 更新 low[u]low[u] min(low[u], low[v]);// 判断是否为割点if (parent[u] -1 childCount 1) { // 根节点且有两个以上子树isCutPoint true;}if (parent[u] ! -1 low[v] dfn[u]) { // 非根节点且满足条件isCutPoint true;}} else if (v ! parent[u]) { // 如果 v 已被访问且不是父节点low[u] min(low[u], dfn[v]); // 更新 low[u]}}// 如果是割点加入结果if (isCutPoint) {cutPoints.push_back(u);}};// 遍历每个节点进行 DFSfor (int i 0; i n; i) {if (!visited[i]) {dfs(i);}}return cutPoints; // 返回割点列表
}// 求解割边的函数
vectorpairint, int findBridges(const vectorvectorint graph) {int n graph.size();vectorpairint, int bridges; // 存储割边vectorint dfn(n, -1), low(n), parent(n, -1); // 初始化 dfn, low, parent 数组vectorbool visited(n, false); // 记录节点是否已被访问int time 0; // 时间戳// DFS 函数functionvoid(int) dfs [](int u) {visited[u] true; // 标记节点 u 为已访问dfn[u] low[u] time; // 设置 dfn 和 low 值// 遍历邻接节点for (int v : graph[u]) {if (!visited[v]) { // 如果 v 未被访问parent[v] u; // 设置 v 的父节点为 udfs(v); // 递归调用 DFS// 更新 low[u]low[u] min(low[u], low[v]);// 判断是否为割边if (low[v] dfn[u]) {bridges.push_back({u, v}); // 记录割边}} else if (v ! parent[u]) { // 如果 v 已被访问且不是父节点low[u] min(low[u], dfn[v]); // 更新 low[u]}}};// 遍历每个节点进行 DFSfor (int i 0; i n; i) {if (!visited[i]) {dfs(i);}}return bridges; // 返回割边列表
}例题
P3388 【模板】割点割顶 给出一个 n 个点m 条边的无向图求图的割点。
#include bits/stdc.h
using namespace std;
vectorint findCutPoints(const vectorvectorint graph);
signed main() {int n,m;cinnm;vectorvectorint G(n1);while(m--){int u,v;cinuv;G[u].push_back(v);G[v].push_back(u);}vectorint CutPointsfindCutPoints(G);coutCutPoints.size()endl;sort(CutPoints.begin(),CutPoints.end());for(int p:CutPoints)coutp ;return 0;
}P1656 炸铁路 将军uim需要选择一条铁路进行炸毁以使得B国的物流系统瘫痪导致至少存在两个城市无法通过铁路相互到达。要选择的铁路被称为“关键铁路”。
#include bits/stdc.h
using namespace std;
vectorpairint, int findBridges(const vectorvectorint graph);
signed main() {int n,m;cinnm;vectorvectorint G(n1);while(m--){int u,v;cinuv;G[u].push_back(v);G[v].push_back(u);}vectorpairint, int BridgesfindBridges(G);for(auto[x,y]:Bridges)if(xy)swap(x,y);sort(Bridges.begin(),Bridges.end());for(auto[x,y]:Bridges)coutx yendl;return 0;
}
