1 介绍

本博客用来记录无向图的双连通分量的相关题目。

以下所有概念都是针对无向图而言的。
桥：本质是边，去掉它，图就不连通了。这样的边叫作桥。
边双连通分量：不包含桥的连通块，且边的数目最大。

割点：本质是结点，去掉它（即去掉这个结点和它所关联的边），图就不连通了。这样的结点叫作割点。
点双连通分量：不包含割点的连通块，且结点的数目最大。

边双连通分量的求解方法：引入时间戳，与有向图强连通分量的求解方法类似。

结论1：对于有向图，至少需要加多少条边，能将此图变成一个强连通分量。答案是max(p, q)，其中p是起点个数（即入度为0的结点个数），q是终点个数（即出度为0的结点个数）。

结论2：对于无向图，至少需要加入多少条边，能将此图变成一个边双连通分量。答案是(cnt + 1) / 2。其中cnt是指出度和入度皆为为1的结点数目。

点双连通分量的求解方法：

2 训练

题目1：395冗余路径

C++代码如下，

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 5010, M = 20010;int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int id[N], dcc_cnt;
bool is_bridge[M];
int d[N];void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}void tarjan(int u, int from) {dfn[u] = low[u] = ++timestamp;stk[++top] = u;for (int i = h[u]; ~i; i = ne[i]) {int j = e[i];if (!dfn[j]) {tarjan(j, i);low[u] = min(low[u], low[j]);if (dfn[u] < low[j]) {is_bridge[i] = is_bridge[i ^ 1] = true;}} else if (i != (from ^ 1)) {low[u] = min(low[u], dfn[j]);}}if (dfn[u] == low[u]) {++dcc_cnt;int y;do {y = stk[top--];id[y] = dcc_cnt;} while (y != u);}
}int main() {cin >> n >> m;memset(h, -1, sizeof h);while (m--) {int a, b;cin >> a >> b;add(a, b), add(b, a);}tarjan(1, -1);for (int i = 0; i < idx; ++i) {if (is_bridge[i]) {d[id[e[i]]]++;}}int cnt = 0;for (int i = 1; i <= dcc_cnt; ++i) {if (d[i] == 1) {cnt++;}}printf("%d\n", (cnt + 1) / 2);return 0;
}

题目2：1183电力

C++代码如下，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 10010, M = 30010;int n, m;
int h[N], e[M], ne[M], idx;
int dfn[M], low[N], timestamp;
int root, ans;void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}void tarjan(int u) {dfn[u] = low[u] = ++timestamp;int cnt = 0;for (int i = h[u]; ~i; i = ne[i]) {int j = e[i];if (!dfn[j]) {tarjan(j);low[u] = min(low[u], low[j]);if (low[j] >= dfn[u]) cnt++;} else {low[u] = min(low[u], dfn[j]);}}if (u != root) cnt++;ans = max(ans, cnt);return;
}int main() {while (scanf("%d%d", &n, &m), n || m) {memset(dfn, 0, sizeof dfn);memset(h, -1, sizeof h);idx = timestamp = 0;while (m--) {int a, b;scanf("%d%d", &a, &b);add(a, b), add(b, a);}ans = 0;int cnt = 0;for (root = 0; root < n; root++) {if (!dfn[root]) {cnt++;tarjan(root);}}printf("%d\n", ans + cnt - 1);}return 0;
}

题目3：396矿场搭建

C++代码如下，

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>using namespace std;typedef unsigned long long ULL;const int N = 1010, M = 1010;int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int dcc_cnt;
vector<int> dcc[N];
bool cut[N];
int root;void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}void tarjan(int u) {dfn[u] = low[u] = ++ timestamp;stk[++top] = u;if (u == root && h[u] == -1) {dcc_cnt ++;dcc[dcc_cnt].push_back(u);return;}int cnt = 0;for (int i = h[u]; ~i; i = ne[i]) {int j = e[i];if (!dfn[j]) {tarjan(j);low[u] = min(low[u], low[j]);if (dfn[u] <= low[j]) {cnt++;if (u != root || cnt > 1) cut[u] = true;++dcc_cnt;int y;do {y = stk[top--];dcc[dcc_cnt].push_back(y);} while (y != j);dcc[dcc_cnt].push_back(u);}} else {low[u] = min(low[u], dfn[j]);}}
}int main() {int T = 1;while (cin >> m, m) {for (int i = 1; i <= dcc_cnt; ++i) dcc[i].clear();idx = n = timestamp = top = dcc_cnt = 0;memset(h, -1, sizeof h);memset(dfn, 0, sizeof dfn);memset(cut, 0, sizeof cut);while (m--) {int a, b;cin >> a >> b;n = max(n, a), n = max(n, b);add(a, b), add(b, a);}for (root = 1; root <= n; ++root) {if (!dfn[root]) {tarjan(root);}}int res = 0;ULL num = 1;for (int i = 1; i <= dcc_cnt; ++i) {int cnt = 0;for (int j = 0; j < dcc[i].size(); ++j) {if (cut[dcc[i][j]]) {cnt++;}}if (cnt == 0) {if (dcc[i].size() > 1) res += 2, num *= dcc[i].size() * (dcc[i].size() - 1) / 2;else res++;} else if (cnt == 1) res++, num *= dcc[i].size() - 1;}printf("Case %d: %d %llu\n", T++, res, num);}return 0;
}