模板及讲解
双连通分量
一个子图中任意两个点之间有至少两条点不相同的路径，则这个子图就是点-双连通分量(无割点)
一个子图中任意两个点之间有至少两条边不相同的路径，则这个子图就是边-双连通分量(无桥)
通俗来说，一个点-双连通分量中删除任意一个点都不会使原图变成多个连通块，一个边-双连通分量中删除任意一条边都不会使原图变成多个连通块
每个点-双连通分量就是一堆环套环，边-双连通分量一定是点-双连通分量
1 任意两个点-双连通分量至多有一个交点割顶
2 桥不在任何边-双连通分量中
1 割点对应点-双连通分量，栈存的是边
2 桥对应边-双连通分量，栈存的是点
相关代码
求割点代码
// 本代码不能处理重边问题，重边就记录父亲边的 ID，只有父亲边的 ID 不能更新 low
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
const int MAXN = 100000 + 5;
int n, m;
vector<int> G[MAXN];
int iscut[MAXN], low[MAXN], dn[MAXN], tb;
void tarjan(int u, int fa) {
low[u] = dn[u] = ++tb;
int child = 0;
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (v == fa) continue;
if (dn[v] == 0) {
child++, tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= dn[u]) iscut[u] = true;//u 是割点
} else if (dn[v] < dn[u]) low[u] = min(low[u], dn[v]);//防重复更新
}
if (fa < 0 && child == 1) iscut[u] = 0;//特判开始点
}
void clean() {
tb = 0;
for (int i = 1; i <= n; ++i) G[i].clear(), iscut[i] = low[i] = dn[i] = 0;
}
void solve() {
clean();
for (int a, b, i = 1;i <= m; ++i) scanf("%d%d", &a, &b), G[a].push_back(b), G[b].push_back(a);
for (int i = 1;i <= n; ++i) if (!dn[i]) tarjan(i, -1);
int ans = 0;
for (int i = 1; i <= n; ++i) if (iscut[i]) ans++;
printf("%d\n", ans);
for (int i = 1; i <= n; ++i) if (iscut[i]) printf("%d ", i);
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}
求桥代码
见 边-双连通分量缩点代码 中注释
边-双连通分量缩点代码
方法与强连通分量 Tarjan 基本一致
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using std::cin; using std::cout; using std::endl;
const int MAXN = 300000 + 5;
struct edge {int v, nxt;} ed[MAXN * 2], ED2[MAXN * 2];
int n, m, en, EN2, hd[MAXN], HD2[MAXN];
int bcc_tot, bcc_belong[MAXN], sz, dfn[MAXN], low[MAXN];
std::stack<int > s;
void ins(int x, int y) {ed[++en] = (edge){y, hd[x]}, hd[x] = en;}
void INS2(int x, int y) {ED2[++EN2] = (edge){y, HD2[x]}, HD2[x] = EN2;}
void tarjan(int u, int fa) {//边双连通缩点部分
dfn[u] = low[u] = ++sz, s.push(u);
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (e.v == fa) continue;
if (!dfn[e.v]) tarjan(e.v, u), low[u] = std::min(low[u], low[e.v]);
else low[u] = std::min(low[u], dfn[e.v]);
}
if (low[u] == dfn[u]) {//(u, fa(u))是桥, 栈存的是点
int e; bcc_tot++;
do {
e = s.top(); s.pop();
bcc_belong[e] = bcc_tot;
} while (e != u);
}
}
int dis[MAXN];
void dfs(int u, int fa) {
dis[u] = dis[fa] + 1;
for (int i = HD2[u]; i > 0; i = ED2[i].nxt) {
edge &e = ED2[i];
if (e.v != fa) dfs(e.v, u);
}
}
void clean() {
en = EN2 = 0;
ms(hd, 0), ms(HD2, 0);
scc_tot = sz = 0, ms(dfn, 0);
}
int solve() {
clean();
for (int x, y, i = 1; i <= m; i++) scanf("%d%d", &x, &y), ins(x, y), ins(y, x);
for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, 0);//边双连通缩点部分
for (int u = 1; u <= n; u++) {
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (bcc_belong[u] != bcc_belong[e.v]) INS2(bcc_belong[u], bcc_belong[e.v]);
}
}
ms(dis, 0); dfs(1, 0);
int S = 1; for (int i = 2; i <= bcc_tot; i++) if (dis[i] > dis[S]) S = i;
dfs(S, 0);
int T = 1; for (int i = 2; i <= bcc_tot; i++) if (dis[i] > dis[T]) T = i;
printf("%d\n", dis[T] - 1);
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}
点-双连通分量缩点代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<climits>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
struct edge {int u, v, nxt;} ed[MAXN * 2];
int n, m, en, hd[MAXN];
int sz, dfn[MAXN], low[MAXN], bcc_tot, bcc_belong[MAXN], bcc_node_num[MAXN], bcc_edge_num[MAXN];
std::vector<int > bcc_edge[MAXN], ans;//每个 bcc 的边
std::stack<int > st;
void ins(int x, int y) {ed[++en] = (edge){x, y, hd[x]}, hd[x] = en;}
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++sz;
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (e.v == fa) continue;
if (!dfn[e.v]) {
st.push(i), tarjan(e.v, u), low[u] = std::min(low[u], low[e.v]);
if (low[e.v] >= dfn[u]) {
bcc_edge[++bcc_tot].clear();
int whw;
do {
whw = st.top(), st.pop();
++bcc_edge_num[bcc_tot], bcc_edge[bcc_tot].push_back(whw);
if (bcc_belong[ed[whw].u] != bcc_tot) ++bcc_node_num[bcc_tot], bcc_belong[ed[whw].u] = bcc_tot;
if (bcc_belong[ed[whw].v] != bcc_tot) ++bcc_node_num[bcc_tot], bcc_belong[ed[whw].v] = bcc_tot;
} while (!(ed[whw].u == u && ed[whw].v == e.v));
}
}
else if(dfn[e.v] < dfn[u]) st.push(i), low[u] = std::min(low[u], dfn[e.v]);//防重复更新
}
}
void clean() {
bcc_tot = sz = en = 0, ms(hd, -1), ms(bcc_node_num, 0), ms(bcc_edge_num, 0), ms(bcc_belong, 0);
}
int solve() {
clean();
for (int u, v, i = 1; i <= m; i++) scanf("%d%d", &u, &v), ins(u, v), ins(v, u);
for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, 0);
for (int i = 1; i <= bcc_tot; i++) {
if (bcc_edge_num[i] == bcc_node_num[i] && bcc_edge_num[i])
for (int j = 0; j < (int)bcc_edge[i].size(); j++) ans.push_back(bcc_edge[i][j]);
}
std::sort(ans.begin(), ans.end());
printf("%d\n", (int)ans.size());
for (int i = 0; i < (int)ans.size(); i++) printf("%d ", (ans[i] + 1) / 2);
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}
1、边-双连通分量缩点
Q：模板题。
解：模板题。
例题：CF 1000E
