364. 网络

发表于 分类于 阅读次数： Waline： 本文字数： 587 阅读时长 ≈ 2 分钟

考点

  • 双连通分量
  • 并查集

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 50, maxm = 2e5 + 50;
int n, m, tot, head[maxn], ver[maxm << 1], nxt[maxm << 1];
int num, dcc, c[maxn], dfn[maxn], low[maxn];
bool bridge[maxm << 1];
// 缩点的新树
int ans, tc, hc[maxn], vc[maxm << 1], nc[maxm << 1], d[maxn], fa[maxn];
// 新树的父亲节点
int go[maxn];

void add(int x, int y) { ver[++tot] = y, nxt[tot] = head[x], head[x] = tot; }

void add_c(int x, int y) { vc[++tc] = y, nc[tc] = hc[x], hc[x] = tc; }

int get(int x) { return x == fa[x] ? x : (fa[x] = get(fa[x])); }

void tarjan(int x, int in_edge) {
  dfn[x] = low[x] = ++num;
  for (int i = head[x]; i; i = nxt[i]) {
    int y = ver[i];
    if (!dfn[y]) {
      tarjan(y, i);
      low[x] = min(low[x], low[y]);
      if (low[y] > dfn[x]) {
        bridge[i] = bridge[i ^ 1] = 1;
      }
    } else if (i != (in_edge ^ 1)) {
      low[x] = min(low[x], dfn[y]);
    }
  }
}

void dfs(int x) {
  c[x] = dcc;
  for (int i = head[x]; i; i = nxt[i]) {
    int y = ver[i];
    if (bridge[i] || c[y]) continue;
    dfs(y);
  }
}

void dfs_c(int x) {
  for (int i = hc[x]; i; i = nc[i]) {
    int y = vc[i];
    if (d[y]) continue;
    d[y] = d[x] + 1;
    go[y] = x;
    dfs_c(y);
  }
}

void calc(int x, int y) {
  // x，y可能已经不是桥了
  x = get(x), y = get(y);
  while (x != y) {
    if (d[x] < d[y]) swap(x, y);
    if (x == 1) break;
    // x到go[x]的边全部变成非桥边
    fa[x] = get(go[x]);
    x = get(x);
    --ans;
  }
}

int main() {
  int x, y, q, t = 0;
  while (~scanf("%d%d", &n, &m) && n) {
    memset(head, 0, sizeof(head));
    memset(hc, 0, sizeof(hc));
    memset(d, 0, sizeof(d));
    memset(c, 0, sizeof(c));
    memset(dfn, 0, sizeof(dfn));
    memset(bridge, 0, sizeof(bridge));
    tot = tc = 1;
    dcc = 0;
    for (int i = 1; i <= m; ++i) {
      scanf("%d%d", &x, &y);
      add(x, y), add(y, x);
    }
    tarjan(1, 0);
    // 缩点
    for (int i = 1; i <= n; ++i) {
      if (!c[i]) {
        ++dcc;
        dfs(i);
      }
    }
    // 建新树
    for (int i = 2; i <= tot; i += 2) {
      x = ver[i ^ 1], y = ver[i];
      if (c[x] != c[y]) {
        add_c(c[x], c[y]), add_c(c[y], c[x]);
      }
    }
    ans = dcc - 1, d[1] = 1, dfs_c(1);
    for (int i = 1; i <= dcc; i++) fa[i] = i;
    printf("Case %d:\n", ++t);
    scanf("%d", &q);
    for (int i = 1; i <= q; ++i) {
      scanf("%d%d", &x, &y);
      if (c[x] != c[y]) calc(c[x], c[y]);
      printf("%d\n", ans);
    }
    puts("");
  }
  return 0;
}

思路

缩点之后，就是一棵树。

如果两个点在同一个边双，加一条边并不会影响桥的个数；

如果两个点不在同一个边双，加一条边则会变成环，环内所有桥都变成非桥边。

由于只能一条条边向上走，所以不需要LCA；但依然需要使用并查集来跳过非桥边以加速。