题目大意
给定一个 $n$ 个点 $m$ 条边的无向图，问至少再加几条边就能使得整个图形成一个边双联通分量。
边双联通分量的定义：一个图中的任意两个结点之间都有两条路径，满足它们的边没有交。
数据范围：$n, m \le 10^6$。
思路分析
不难发现答案为：根据边双联通分量缩点后得到的森林中的每一个联通块的叶子结点的个数的一半向上取整之和。
时间复杂度 $O(n + m)$。
代码实现
1 | |
2 | |
3 | using namespace std; |
4 | |
5 | const int maxn = 1e6, maxm = maxn * 2; |
6 | int n, m, u[maxm + 3], v[maxm + 3]; |
7 | int tm, dfn[maxn + 3], low[maxn + 3], top, st[maxn + 3]; |
8 | int cnt, bel[maxn + 3], deg[maxn + 3], cur; |
9 | int tot, ter[maxm + 3], nxt[maxm + 3], lnk[maxn + 3]; |
10 | bool vis[maxn + 3]; |
11 | |
12 | void add(int u, int v) { |
13 | ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot; |
14 | } |
15 | |
16 | int adj(int x) { |
17 | return x & 1 ? x + 1 : x - 1; |
18 | } |
19 | |
20 | void tarjan(int u, int e = 0) { |
21 | dfn[u] = low[u] = ++tm; |
22 | st[++top] = u; |
23 | for (int i = lnk[u], v; i; i = nxt[i]) { |
24 | v = ter[i]; |
25 | if (!dfn[v]) { |
26 | tarjan(v, i); |
27 | low[u] = min(low[u], low[v]); |
28 | } else if (i != adj(e)) { |
29 | low[u] = min(low[u], dfn[v]); |
30 | } |
31 | } |
32 | if (dfn[u] == low[u]) { |
33 | cnt++; |
34 | do { |
35 | bel[st[top]] = cnt; |
36 | } while (st[top--] != u); |
37 | } |
38 | } |
39 | |
40 | void dfs(int u, int pa = 0) { |
41 | if (pa) { |
42 | cur -= (deg[u] == 1) + (deg[pa] == 1); |
43 | deg[u]++, deg[pa]++; |
44 | cur += (deg[u] == 1) + (deg[pa] == 1); |
45 | } |
46 | vis[u] = true; |
47 | for (int i = lnk[u], v; i; i = nxt[i]) { |
48 | v = ter[i]; |
49 | if (!vis[v]) { |
50 | dfs(v, u); |
51 | } |
52 | } |
53 | } |
54 | |
55 | int main() { |
56 | scanf("%d %d", &n, &m); |
57 | for (int i = 1; i <= m; i++) { |
58 | scanf("%d %d", &u[i], &v[i]); |
59 | add(u[i], v[i]), add(v[i], u[i]); |
60 | } |
61 | for (int i = 1; i <= n; i++) { |
62 | if (!dfn[i]) tarjan(i); |
63 | } |
64 | tot = 0; |
65 | for (int i = 1; i <= n; i++) { |
66 | lnk[i] = 0; |
67 | } |
68 | for (int i = 1; i <= m; i++) if (bel[u[i]] != bel[v[i]]) { |
69 | add(bel[u[i]], bel[v[i]]), add(bel[v[i]], bel[u[i]]); |
70 | } |
71 | int ans = 0; |
72 | for (int i = 1; i <= cnt; i++) if (!vis[i]) { |
73 | cur = 0, dfs(i); |
74 | ans += (cur + 1) / 2; |
75 | } |
76 | printf("%d\n", ans); |
77 | return 0; |
78 | } |