板子和常识
https://oi-wiki.org/graph/bcc/
板子用的是 tarjan算法2 的思想
只能跑无向图
-
理论基础
-
SCC部分
对于一个连通分量图，我们很容易想到，在该连通图中有且仅有一个 \(u\) 使得 $\texttt{dfn}_u=\texttt{low}_u $。该结点一定是在深度遍历的过程中，该连通分量中第一个被访问过的结点，因为它的 \(dfn\) 和 \(low\) 值最小，不会被该连通分量中的其他结点所影响。
因此，在回溯的过程中，判定 $\texttt{dfn}_u=\texttt{low}_u $ 是否成立，如果成立，则栈中 \(u\) 及其上方的结点构成一个 SCC。
-
桥与边双联通部分
我们先总结出一个重要的性质，在无向图中，DFS 生成树上的边不是树边就只有非树边。
我们联系一下求强连通分量的方法，在无向图中只要一个分量没有桥，那么在 DFS 生成树上，它的所有点都在同一个强连通分量中。
反过来，在 DFS 生成树上的一个强连通分量，在原无向图中是边双连通分量。
可以发现，求边双连通分量的过程实际上就是求强连通分量的过程
-
-
板子解释
class EdgeBC { const std::vector<std::vector<int>> &e;//存原来的无向图 std::vector<int> stk; // stack int r = 0, cur = 0; void dfs(int x, int fa) {//dfs生成树上跑强连通分量 dfn[x] = low[x] = cur++; stk[++r] = x;//把本次递归到的所有节点（也就是该联通快所有节点）压栈 for (int y : e[x]) { if (y == fa) {//如果邻接节点 y 是当前节点的父节点，则跳过（将 fa 反转的目的是为了避免将父节点自身当作回边处理）。 fa = ~fa; continue; } //强连通分量 if (dfn[y] == -1) { dfs(y, x); low[x] = std::min(low[x], low[y]); } else { low[x] = std::min(low[x], dfn[y]); } } if (dfn[x] == low[x]) {//符合强连通分量条件 int y; do { y = stk[r--]; bel[y] = cntBlock;//bel[y](y结点对应的联通快编号) } while (y != x); cntBlock += 1; } } public: // original graph std::vector<int> dfn, low, bel, cutDeg;//bel[y](y结点对应的联通快编号) // shrinking graph std::vector<std::vector<int>> g;//由桥构成的无根树 int cntBlock = 0, componentNum = 0; EdgeBC(const std::vector<std::vector<int>> &e) : e(e), dfn(e.size(), -1), low(e.size()), bel(e.size(), -1), cutDeg(e.size()) { int n = e.size(); q.assign(n + 1, 0); for (int i = 0; i < n; i++) { if (dfn[i] == -1) { componentNum += 1; dfs(i, -1); } } g.resize(cntBlock); for (int x = 0; x < n; x++) { for (int y : e[x]) { if (bel[x] == bel[y]) continue; g[bel[x]].push_back(bel[y]); } } } };
怎么用
- 求每个边双联通分量
由理论基础中：
反过来，在 DFS 生成树上的一个强连通分量，在原无向图中是边双连通分量。
显然，强连通分量就是答案
class EdgeBC {
const std::vector<std::vector<int>> &e;
std::vector<int> q; // stack
int r = 0, cur = 0;
void dfs(int x, int fa) {
dfn[x] = low[x] = cur++;
q[++r] = x;
for (int y : e[x]) {
if (y == fa) {
fa = ~fa;
continue;
}
if (dfn[y] == -1) {
dfs(y, x);
low[x] = std::min(low[x], low[y]);
} else {
low[x] = std::min(low[x], dfn[y]);
}
}
if (dfn[x] == low[x]) {
int y;
std::vector<int> res{x};
do {
y = q[r--];
bel[y] = cntBlock;
if (y != x) res.push_back(y);//把每个强连通分量统计进去就行
} while (y != x);
resEdgeBC.push_back(res);
cntBlock += 1;
}
}
public:
// original graph
std::vector<int> dfn, low, bel, cutDeg;
std::vector<std::vector<int>> resEdgeBC;
// shrinking graph
std::vector<std::vector<int>> g;//就是由割边组成的无根树
//g.size() - 1就是割边数量
int cntBlock = 0, componentNum = 0;
EdgeBC(const std::vector<std::vector<int>> &e)
: e(e), dfn(e.size(), -1), low(e.size()), bel(e.size(), -1), cutDeg(e.size()) {
int n = e.size();
q.assign(n + 1, 0);
for (int i = 0; i < n; i++) {
if (dfn[i] == -1) {
componentNum += 1;
dfs(i, -1);
}
}
g.resize(cntBlock);
for (int x = 0; x < n; x++) {
for (int y : e[x]) {
if (bel[x] == bel[y])
continue;
g[bel[x]].push_back(bel[y]);
}
}
}
};
void solve()
{
int n, m; std::cin >> n >> m;
std::vector adj(n, std::vector<int>()); for (int i = 0, u, v; i < m; i++) {std::cin >> u >> v; --u; --v; adj[u].push_back(v); adj[v].push_back(u);}
auto res{EdgeBC(adj).resEdgeBC};
std::cout << std::size(res) << '\n';
for (auto& g : res) {
std::cout << std::size(g) << ' '; for (auto& x : g) {std::cout << x + 1 << ' ';} std::cout << "\n";
}
}
-
求桥
https://ac.nowcoder.com/acm/contest/81601/D
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=70636428
由桥的定义：
对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。
那么对于一条边，如果两个顶点不属于同一个联通快，那显然就是一个桥。
对于该板子的使用，即对于 bel[x] != bel[y]，\((x, y), (y, x)\) 都是桥
class EdgeBC {
const std::vector<std::vector<int>> &e;
std::vector<int> q; // stack
int r = 0, cur = 0;
void dfs(int x, int fa) {
dfn[x] = low[x] = cur++;
q[++r] = x;
for (int y : e[x]) {
if (y == fa) {
fa = ~fa;
continue;
}
if (dfn[y] == -1) {
dfs(y, x);
low[x] = std::min(low[x], low[y]);
} else {
low[x] = std::min(low[x], dfn[y]);
}
}
if (dfn[x] == low[x]) {
int y;
do {
y = q[r--];
bel[y] = cntBlock;
} while (y != x);
cntBlock += 1;
}
}
public:
// original graph
std::vector<int> dfn, low, bel, cutDeg;
std::set<std::pair<int, int>> S_bridge;
// shrinking graph
std::vector<std::vector<int>> g;//就是由割边组成的无根树
//g.size() - 1就是割边数量
int cntBlock = 0, componentNum = 0;
EdgeBC(const std::vector<std::vector<int>> &e)
: e(e), dfn(e.size(), -1), low(e.size()), bel(e.size(), -1), cutDeg(e.size()) {
int n = e.size();
q.assign(n + 1, 0);
for (int i = 0; i < n; i++) {
if (dfn[i] == -1) {
componentNum += 1;
dfs(i, -1);
}
}
g.resize(cntBlock);
for (int x = 0; x < n; x++) {
for (int y : e[x]) {
if (bel[x] == bel[y])
continue;
g[bel[x]].push_back(bel[y]);
S_bridge.emplace(x, y); S_bridge.emplace(y, x);//符合条件，加入集合
}
}
}
};