- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
文章图片全部来自 Oi-wiki,部分图片加以修改 。
前面我们在学 tarjan 算法时,提到过强连通分量,即有向图上的环,那么无向图上是否也有强连通分量呢?很遗憾,没有 但是,无向图有双连通分量!分为点双连通和边双连通(下面简称点双和边双).
在一张联通的无向图中,对于两个点 \(x\) 和 \(y\) ,删去图上的任意一条边,两个点始终保持联通,则这两个点是边双连通。 边双连通分量,即 极大边双连通子图 ,边双连通分量中的任意两点都是边双连通的,且如果加入一个不属于该子图的点,都会导致这个图不再满足两两之间边双的性质。 在无向图中。删掉一条边,导致两个图不连通了,这条边就是 割边 ,也叫做 桥 .
边双连通具有传递性,即如果 \(x\) 与 \(y\) 边双连通, \(y\) 与 \(z\) 边双连通,则 \(x\) 与 \(z\) 也边双连通。 如图,在这张图中, \(A\) 与 \(B\) 边双连通, \(B\) 与 \(C\) 边双连通,根据传递性, \(A\) 与 \(C\) 边双连通。(即使不跟据传递性,他们也的确是边双连通) 。
如图,绿色的边和黑色的边都是树边,红色的边是返祖边。 我们发现,每一条返祖边都对应着一条树上的简单路径,即覆盖了树上的一些边,覆盖了的边我们用绿边表示,黑色的边没有被覆盖。我们如果删去返祖边或者任意一条绿边,都不会影响图的连通性(如果删掉返祖边就从绿边走,如果删掉绿边就从返祖边走),但是,如果我们删掉黑边,那么整个图就会被一分为二,不再保持联通, 这些黑色的边就是桥 ,同时 返祖边和绿边一定不是桥 。 这样,我们只要找到所有的桥,就能确定边双连通分量了。 找边双连通分量,我们可以用 tarjan 算法.
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++ tim; // 打上时间戳
for (int i = h[u], v; i; i = e[i].nxt) {
v = e[i].v;
if ((i ^ 1) == fa) continue;
if (!dfn[v]) { // 如果这个点从未被搜过
tarjan(v, i); // 继续往下搜
low[u] = min(low[u], low[v]); // 正常更新 low 值
if (low[v] > dfn[u]) { // 如果 v 点无法通过返祖边向上返回到 u 点即往上
e[i].ok = e[i ^ 1].ok = 1; // 那么这条边就是桥
}
// 不理解的话可以想一想,v 点不管怎么向上都不能到达 u 点即更靠上的位置,那 u -> v 这条边就没有被返祖边覆盖,它就是桥
}
else { // 如果这个点已经被搜过了(说明这条边是返祖边)
low[u] = min(low[u], dfn[v]); // 更新 low 值(比较的是 dfn[v],不是 low[v])
}
}
}
有两种方式,像找强连通分量那样用一个栈,或者标记桥之后再 dfs。 洛谷模板题测试,用栈比标记桥更快一些.
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++ tim;
sta.push_back(u);
for (auto [v, i] : son[u]) {
if (i == fa) continue;
if (! dfn[v]) {
tarjan(v, i);
low[u] = min(low[u], low[v]);
}
else {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
ans[++ dcc].push_back(u);
while (sta.back() != u) {
ans[dcc].push_back(sta.back());
sta.pop_back();
}
sta.pop_back();
}
}
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++ tim;
for (auto [v, i] : son[u]) {
if (i == fa) continue;
if (! dfn[v]) {
tarjan(v, i);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u]) {
ok[i] = 1;
}
}
else {
low[u] = min(low[u], dfn[v]);
}
}
}
void dfs(int u) { // dfn 要清零,你也可以再开一个数组
ans[dcc].push_back(u);
dfn[u] = 1;
for (auto [v, i] : son[u]) {
if (dfn[v] || ok[i]) continue;
dfs(v);
}
}
在一张联通的无向图中,对于两个点 \(x\) 和 \(y\) ,删去图上的任意一个点(不能删去 \(x\) 和 \(y\) ),两个点始终保持联通,则这两个点是点双连通.
删去一个点,会删掉这个点以及这个点所连接的所有的边,所以桥连接的两个点都是割点.
点双连通分量,即 极大点双连通子图 ,点双连通分量中的任意两点都是点双连通的,且如果加入一个不属于该子图的点,都会导致这个图不再满足两两之间点双的性质。 在无向图中。删掉一个点,导致两个图不连通了,这个点就是 割点 .
点双连通没有传递性,即如果 \(x\) 和 \(y\) 点双联通, \(y\) 和 \(z\) 点双联通, \(x\) 和 \(z\) 不一定点双联通。 举个例子。 \(A\) 与 \(B\) 点双连通, \(B\) 与 \(C\) 点双连通,但是 \(A\) 与 \(C\) 并不是点双连通。(割点为 \(B\) ) 。
如图,黑色的边是树边,红色的边是返祖边,每一条返祖边对应着一条简单路径。 现在,我们将每一条边看作是一个点,即图上蓝色的点,返祖边所覆盖的简单路径上的边都连上边,即图上的蓝边。 这样,要判断点是否为割点,只要判断这个点连出去的边是否在一个连通分量里,都在一个连通分量里,就不是割点,否则就是割点 这里还有另一种做法。 对于某个顶点 \(u\) ,如果存在至少一个顶点 \(v\) ,使得 low[v] \(\geq\) dfn[u] ,即不能回到祖先,那么 \(u\) 点为割点。 但这个做法唯独不适用于搜索树的起始点,即搜索树的根,如果根只有一个子树,那我们把根节点删去,对图的连通性不会有任何影响,即根节点不是割点,如果根节点有着至少两个子树,那么根节点就是割点.
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++ cnt;
int son = 0;
for (int i = h[u], v; i; i = e[i].nxt) {
v = e[i].v;
if (v == fa) continue;
if (!dfn[v]) {
++ son;
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
ok[u] = 1;
++ dcc;
}
}
else {
low[u] = min(low[u], dfn[v]);
}
}
if (fa == 0 && son < 2) ok[u] = 0;
}
在题目中,桥一般出现在“给定一张无向图,问是否有一种方案,能给定向,同时保证每个点都能走到”这样类似的题目上,在这道题中,有桥就没有可行方案,倘若要输出方案,我们可以利用 dfs 生成树。 由于边双比点双有着更好的性质,所以一般题目都是有关边双的.
vector
来写 tarjan 优点:动态空间,方便。 缺点: 慢! 上面的代码我们也看到了,有些题目有重边,用一般的 vector 存图方式判断是否走过重边,这里有一个方式可以实现用 vector 来找重边,那就是将 vector 的变量类型改成 pair ,第一个元素存到达的节点,第二个元素存这条边的编号,如果不保险可以再开一个 vector 、结构体或两个数组来存第 \(i\) 条边的两个端点的编号,像这样.
e.push_back({0, 0});
for (int i = 1, x, y; i <= m; ++ i) {
scanf("%d%d", &x, &y);
son[x].push_back({y, i});
son[y].push_back({x, i});
e.push_back({x, y});
}
这样,我们在 tarjan 判重边的的过程中可以直接判断编号了.
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++ tim;
for (auto [v, i] : son[u]) {
if (i == fa) continue;
if (! dfn[v]) {
tarjan(v, i);
low[u] = min(low[v], low[u]);
if (low[v] > dfn[u]) {
ok[i] = 1;
}
}
else {
low[u] = min(low[u], dfn[v]);
}
}
}
对于找割点,我们直接用 vector 就行了,这里不存在任何限制,就是会慢.
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++ cnt;
st[++ top] = u;
int ch = 0;
for (int v : son[u]) {
if (v == fa) continue;
if (!dfn[v]) {
++ ch;
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
ok[u] = 1;
++ dcc;
while (st[top + 1] != v) {
ans[dcc].push_back(st[top --]);
}
ans[dcc].push_back(u);
}
}
else {
low[u] = min(low[u], dfn[v]);
}
}
if (fa == 0 && ch == 0) ans[++ dcc].push_back(u);
if (fa == 0 && ch < 2) ok[u] = 0;
}
都是来源于洛谷的模板题 P8436 【模板】边双连通分量 。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 5e5 + 5;
const int M = 2e6 + 5;
int n, m, cnt = 1, tim, top, dcc;
int h[N], dfn[N], low[N];
bool ok[M];
vector<pii> son[N];
vector<int> ans[N], sta;
struct edge {
int v, nxt;
bool ok;
} e[M << 1];
void add(int u, int v) {
e[++ cnt].nxt = h[u];
e[h[u] = cnt].v = v;
}
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++ tim;
sta.push_back(u);
for (auto [v, i] : son[u]) {
if (i == fa) continue;
if (! dfn[v]) {
tarjan(v, i);
low[u] = min(low[u], low[v]);
}
else {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
ans[++ dcc].push_back(u);
while (sta.back() != u) {
ans[dcc].push_back(sta.back());
sta.pop_back();
}
sta.pop_back();
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1, x, y; i <= m; ++ i) {
scanf("%d%d", &x, &y);
son[x].push_back({y, i});
son[y].push_back({x, i});
}
for (int i = 1; i <= n; ++ i) {
if (!dfn[i]) {
tarjan(i, 0);
}
}
printf("%d\n", dcc);
for (int i = 1; i <= dcc; ++ i) {
int siz = ans[i].size();
printf("%d ", siz);
for (int j : ans[i]) {
printf("%d ", j);
}
putchar('\n');
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 5e5 + 5;
const int M = 2e6 + 5;
int n, m, cnt = 1, tim, top, dcc;
int h[N], dfn[N], low[N];
bool ok[M];
vector<int> ans[N];
vector<pii> son[N];
struct edge {
int v, nxt;
bool ok;
} e[M << 1];
void add(int u, int v) {
e[++ cnt].nxt = h[u];
e[h[u] = cnt].v = v;
}
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++ tim;
for (auto [v, i] : son[u]) {
if (i == fa) continue;
if (! dfn[v]) {
tarjan(v, i);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u]) {
ok[i] = 1;
}
}
else {
low[u] = min(low[u], dfn[v]);
}
}
}
void dfs(int u) {
ans[dcc].push_back(u);
dfn[u] = 1;
for (auto [v, i] : son[u]) {
if (dfn[v] || ok[i]) continue;
dfs(v);
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1, x, y; i <= m; ++ i) {
scanf("%d%d", &x, &y);
son[x].push_back({y, i});
son[y].push_back({x, i});
}
for (int i = 1; i <= n; ++ i) {
if (!dfn[i]) {
tarjan(i, 0);
}
}
memset(dfn, 0, sizeof dfn);
for (int i = 1; i <= n; ++ i) {
if (!dfn[i]) {
++ dcc;
dfs(i);
}
}
printf("%d\n", dcc);
for (int i = 1; i <= dcc; ++ i) {
int siz = ans[i].size();
printf("%d ", siz);
for (int j : ans[i]) {
printf("%d ", j);
}
putchar('\n');
}
return 0;
}
P8435 【模板】点双连通分量 。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
const int M = 2e6 + 5;
int n, m, cnt, top, dcc;
int h[N], dfn[N], low[N], st[N];
bool ok[N];
vector<int> son[N], ans[N];
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++ cnt;
st[++ top] = u;
int ch = 0;
for (int v : son[u]) {
if (v == fa) continue;
if (!dfn[v]) {
++ ch;
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
ok[u] = 1;
++ dcc;
while (st[top + 1] != v) {
ans[dcc].push_back(st[top --]);
}
ans[dcc].push_back(u);
}
}
else {
low[u] = min(low[u], dfn[v]);
}
}
if (fa == 0 && ch == 0) ans[++ dcc].push_back(u);
if (fa == 0 && ch < 2) ok[u] = 0;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1, x, y; i <= m; ++ i) {
scanf("%d%d", &x, &y);
son[x].push_back(y);
son[y].push_back(x);
}
cnt = 0;
for (int i = 1; i <= n; ++ i) {
if (!dfn[i]) {
top = 0;
tarjan(i, 0);
}
}
printf("%d\n", dcc);
for (int i = 1; i <= dcc; ++ i) {
printf("%d ", (int)ans[i].size());
for (int j : ans[i]) {
printf("%d ", j);
}
putchar('\n');
}
return 0;
}
最后此篇关于「学习笔记」双连通分量、割点与桥的文章就讲到这里了,如果你想了解更多关于「学习笔记」双连通分量、割点与桥的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我想使用错误组件显示我的错误消息,但不想在 中加载组件对于经过身份验证的用户,导航菜单也不应显示。 我有这样的应用程序组件.. 我有错误处理程序,它使用 router.navigate 路由
我正在尝试获取 RGB 图像,将其转换为 LAB(又名 CIE L* a* b*)色彩空间,然后提取 L* 分量。 这是我的代码: from skimage import io, color from
我在我的一个模型中定义了以下常量。 export const NEWS_TYPE_TEXT = { News: 'News', Interview: 'Intervie
我有一个Electron(6)/Angular(8)应用程序。 在正面( Angular ),我通过IPCRenderer向背面发送一条消息。 在背面,IPCMain接收消息并执行所需的操作,例如,获
我正在尝试在我的应用程序中创建一个可重用的 quickView 模式,以使用 ng-bootstrap modal library 动态加载任何组件。 就我加载文档中所示的相同示例组件而言,它工作正常
我需要将一个名为“photos”的数组从我的 component.ts 传递到 component.html。这是我的 component.ts 文件 export class PhotosCompo
我有一个按钮,单击该按钮会转到新路线并打开附加到该路线的另一个组件。 有没有一种方法可以从 DOM 中删除我们单击以转到不同组件的组件?示例:当单击“单击我返回主页”按钮时,它会打开另一个组件。在这种
这个问题在这里已经有了答案: Detect click outside Angular component (12 个答案) 5天前关闭。 我知道这方面有无数的问题,我尝试了每一个解决方案,但没有一个
我想将显示值的格式传递给 Angular 分量。 例如: format="'(utc, offset) location (tz)'" === '(UTC -04:00) New York (EDT)
我正在使用 Angular 组件将动态图表加载到我的小部件中: 这是我的组件的示例: angular.module("generalApp").component("chartPie", { temp
假设我有一个组件在被点击时发出一个事件,即 @Component({ selector: 'component-checkout-payment', template:
我有一个问题。 我正在处理另一个人的代码,有一个 JFrame 有很多 JSeparators(他用它们作为“面板”的边框)现在我将它们替换为 JBorderedPanel 类,该类遵循与整体相同的边
所以我在这里想做的是制作一个 Angular 组件并将其注入(inject)到我的 Angular 应用程序中。这是 Angular 分量的代码: (function(angular) { 'use
关闭。这个问题需要多问focused 。目前不接受答案。 想要改进此问题吗?更新问题,使其仅关注一个问题 editing this post . 已关闭 4 年前。 Improve this ques
我正在创建一个像这样的可重用组件: submit 我想在属性 isDisabled 为 true 时禁用点击事件,我尝试了类似的操作,但它不起作用。 packages/component/my-b
一种简单的说法是,当 RGB 分量相等时,它们形成灰色。然而,这还不是全部,因为如果它们只有细微的差别,它们看起来仍然是灰色的。 假设观看者具有健康的色彩视觉,我如何确定给定值是否会被视为灰色(大概具
您好我正在尝试使用带 Angular Electron 构建桌面应用程序,主要问题是在用户登录后我找不到正确加载主要组件的方法。正如您在 main.js 中看到的,这是我创建两个窗口(1 个用于登录的
new AngularJS 1.5 中似乎没有“替换”选项组件概念(就像指令一样)。 如果我想要表格行,你有什么建议元素作为组件?就有效的 HTML 而言是不可能的吗? 真实示例:mailBox组件内
我有颜色=#12FFFF。这是这种格式的颜色,其中 12FFFF 是十六进制数。现在我想获取每个独立的 R、G、B 分量的十进制。我该如何在java中做到这一点? 最佳答案 目前尚不清楚你的问题是什么
我需要一些关于 Java 的 ImageIO API 的帮助。我似乎迷失在 ComponentColorModel 类中。我需要逐像素检查 *.png 文件来检测它是灰度图像还是彩色图像。但是,我不知
我是一名优秀的程序员,十分优秀!