「学习笔记」双连通分量、割点与桥

这篇具有很好参考价值的文章主要介绍了「学习笔记」双连通分量、割点与桥。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

文章图片全部来自 \(\texttt{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();
	}
}
  • 标记桥,dfs。
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 【模板】边双连通分量

  • 直接用栈来找边双。
//The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

const int N = 5e5 + 5;
const int M = 2e6 + 5;

using edge = tuple<int, int>;

int n, m, tim;
int dfn[N], low[N];
vector<edge> e[N];
vector<int> st;
vector<vector<int>> ans;

void tarjan(int u, int fi) {
    dfn[u] = low[u] = ++ tim;
    st.emplace_back(u);
    int v, idn;
    for (edge it : e[u]) {
        tie(v, idn) = it;
        if (idn == fi)  continue ;
        if (!dfn[v]) {
            tarjan(v, idn);
            low[u] = min(low[u], low[v]);
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        vector<int> g;
        g.emplace_back(u);
        while (st.back() != u) {
            g.emplace_back(st.back());
            st.pop_back();
        }
        st.pop_back();
        ans.emplace_back(g);
    }
}

int main() {
    n = read<int>(), m = read<int>();
    int x, y;
    rep (i, 1, m, 1) {
        x = read<int>(), y = read<int>();
        e[x].emplace_back(y, i);
        e[y].emplace_back(x, i);
    }
    rep (i, 1, n, 1) {
        if (!dfn[i]) {
            tarjan(i, 0);
        }
    }
    cout << ans.size() << '\n';
    for (vector<int> it : ans) {
        cout << it.size() << ' ';
        for (int v : it) {
            cout << v << ' ';
        }
        putchar('\n');
    }
    return 0;
}
  • 标记桥,通过 dfs 来找边双。
#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 【模板】点双连通分量文章来源地址https://www.toymoban.com/news/detail-435589.html

//The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

const int N = 5e5 + 5;

using val = tuple<int, int>;

int n, m, tim;
int dfn[N], low[N];
vector<int> st;
vector<val> e[N];
vector<vector<int>> dcc;

void tarjan(int u, int fi) {
    int v, idn, ch = 0;
    st.emplace_back(u);
    dfn[u] = low[u] = ++ tim;
    for (val it : e[u]) {
        tie(v, idn) = it;
        if (idn == fi)  continue ;
        if (!dfn[v]) {
            ++ ch;
            tarjan(v, idn);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                int x;
                vector<int> ans;
                do {
                    x = st.back();
                    st.pop_back();
                    ans.emplace_back(x);
                } while (x != v);
                ans.emplace_back(u);
                dcc.emplace_back(ans);
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (!fi && !ch) {
        vector<int> ans;
        ans.emplace_back(u);
        dcc.emplace_back(ans);
    }
}

int main() {
    n = read<int>(), m = read<int>();
    int x, y;
    rep (i, 1, m, 1) {
        x = read<int>(), y = read<int>();
        e[x].emplace_back(y, i);
        e[y].emplace_back(x, i);
    }
    rep (i, 1, n, 1) {
        if (!dfn[i]) {
            tarjan(i, 0);
        }
    }
    cout << dcc.size() << '\n';
    for (vector<int> it : dcc) {
        cout << it.size() << ' ';
        for (int v : it) {
            cout << v << ' ';
        }
        putchar('\n');
    }
    return 0;
}

到了这里,关于「学习笔记」双连通分量、割点与桥的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【图论】强连通分量

    ​  强连通分量(Strongly Connected Components,简称SCC)是图论中的一个概念,用于描述有向图中的一组顶点,其中任意两个顶点之间都存在一条有向路径。换句话说,对于图中的任意两个顶点u和v,如果存在一条从u到v的有向路径,同时也存在一条从v到u的有向路径,那么u和v就属

    2024年02月14日
    浏览(40)
  • 【图论】强连通分量进阶

    强连通分量可以判断环和进行缩点。还有一系列作用.... 这篇文章介绍 缩点 https://www.luogu.com.cn/problem/P2341 我们分析可以知道当一个点没有出度时,则为最受欢迎的牛。但如果有多个出度,则没有最受欢迎的牛。 这是只有一个出度的情况:   这是多个出度的情况: 但为什么要

    2024年02月14日
    浏览(43)
  • 有向图的强连通分量

    对于一个有向图,连通分量:对于分量中任意两点u,v,必然可以从u走到v,且从v走到u. 强连通分量:极大连通分量。 求出强连通分量后,可以通过将强连通分量缩点的方式,将有向图转化成有向无环图。 求强连通分量的方法:tarjan O(n+m),时间复杂度是线性的 1 . 采用dfs来遍历整

    2024年02月10日
    浏览(36)
  • 图的基本概念辨析,包括连通图、极大连通子图、连通分量、强连通图、极大强连通子图等

    概念(1-4)都是针对无向图的   图中从一个顶点到达另一顶点,若存在至少一条路径,则称这两个顶点是连通着的。例如图 1 中,虽然 V1 和 V3 没有直接关联,但从 V1 到 V3 存在两条路径,分别是 V1-›V2-›V3 和 V1-›V4-›V3,因此称 V1 和 V3 之间是连通的。 图 1 顶点之间的连

    2024年02月15日
    浏览(56)
  • 有向图的强连通分量算法

    有向图的强连通分量算法 强连通分量定义 在有向图中,某个子集中的顶点可以直接或者间接互相可达,那么这个子集就是此有向图的一个强连通分量,值得注意的是,一旦某个节点划分为特定的强连通分量后,此顶点不能在其它子树中重复使用,隐含了图的遍历过程和极大

    2024年02月06日
    浏览(71)
  • 第三章 图论 No.9有向图的强连通与半连通分量

    连通分量是无向图的概念,yxc说错了,不要被误导 强连通分量:在一个有向图中,对于分量中的任意两点u,v,一定能从u走到v,且能从v走到u。强连通分量是一些点的集合,若加入其他点,强连通分量中的任意两点就不能互相递达 半连通分量:在一个有向图中,对于分量中

    2024年02月13日
    浏览(47)
  • 团体程序设计天梯赛 L2-013 红色警报(连通分量)

    分数 25 战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序,当失去一个城市导致国家被分裂为多个无法连通的区域时,就发出红色警报。注意:若该国本来就不完全连通,是分裂的k个区域,而失去一个城市并不改变其他城市之间的连通性,则不要发出

    2024年03月13日
    浏览(50)
  • 【学习笔记】无向图的连通性

    定义: 在无向图连通图中,若把点 (x) 删去后整个图就不连通了,则 (x) 为割点(割顶)。 朴素方法: 每次删去一个点,然后判断图是否连通,时间复杂度为 (O(n(n+m))) 。 Tarjan 算法: (dfn_x) : (x) 被 dfs 到的时间戳 (low_x) :在 (x) 及以后被搜索的所有节点的 (low) 值

    2024年02月15日
    浏览(37)
  • ROS自学笔记二十五:导航中目标点与路径规划消息

    在ROS导航中,目标点与路径规划消息通常使用 geometry_msgs/PoseStamped来描述目标点的位置以及使用 nav_msgs/Path 来描述规划路径。以下是这两个消息类型的详细介绍和示例: `geometry_msgs/PoseStamped` 用于表示一个带有时间戳的目标点位置,通常用于发送机器人需要前往的目标点。 以

    2024年02月06日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包