跳转至

点双连通分量

对于一个无向连通图，若删去其中任意一个点，都不会改变图的连通性，则称这个图点双连通。

割点

对于一个无向图，若删去一个点之后，图的连通性发生了变化（连通块数量变多），则称这个节点为图的一个割点。

割点可以使用 Tarjan 算法求出。当且仅当节点 \(u\) 存在一个儿子 \(v\)，满足 low[v] >= dfn[u]，并且 \(u\) 不是 dfs 树的树根且 \(u\) 只连接一条树边，那么节点 \(u\) 是一个割点。

点双连通分量

一个无向图的极大点双连通子图称为点双连通分量。

性质

  • 两个点双最多有一个公共点，并且这个点是割点；
  • 图上每条边都唯一对应一个点双；

有一种看似正确的简单的 dfs 做法：先找出所有割点，然后通过一遍 dfs，ban 掉所有割点，这样每个连通块就是一个点双分量。事实上，在下面这个图上，dfs 不能正确的求出 bcc，因为它无法处理 bcc 仅包含割点的情况：

n=5, m=5
1 4
2 5
2 6
4 5
4 6
5 6

我们必须通过在 Tarjan 中维护栈来求解点双分量。具体的，当我们通过 \((u,v)\) 将 \(u\) 标记为了一个割点，那么将 \(v\) 及以下点双连通的节点与节点 \(u\) 一起，划入一个新的 bcc。在刚进入一个节点 \(u\) 时将 \(u\) 入栈；若发现节点 \(v\) 无法跨过其父亲 \(u\)，那么将栈中 \(v\) 以上的元素全部弹出，加入一个新的 bcc，再把 \(u\) 也加入该 bcc 即可。

代码 
 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
void tarjan(int u, int fe) {
    low[u] = dfn[u] = ++dt;
    sta[++top] = u;
    int chd = 0;
    for(int e = head[u]; e; e = pool[e].next) {
        if(e == fe) continue;
        int v = pool[e].v;
        if(!dfn[v]) {
            ++chd;
            tarjan(v, e ^ 1);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) {
                cut[u] = 1;
                bcc[++bccCnt].push_back(u);
                while(sta[top + 1] != v) {
                    bcc[bccCnt].push_back(sta[top]);
                    --top;
                }
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(!fe && chd == 1) cut[u] = 0;
}

例题 1

给定一个无向图，称一个点是特殊点，当且仅当删除这个点之后图变为一棵树。保证初始无重边自环。请输出所有特殊点。

一个无向连通图是树当且仅当其边数等于点数减一。因此根据每个节点是否是割点，以及它的度数来判断即可。注意一棵树和一个孤立点的情况需要特判。

P3469 [POI2008] BLO-Blockade

给定一个无向连通图，请对每个节点 \(i\) 求出：删除 \(i\) 的所有连边（不包含节点 \(i\) 本身）后，有多少个有序点对 \((x,y)\) 不连通。

\(n\le 10^5,\ m\le 5\times 10^5\)

我们在 Tarjan 中考虑一个节点 \(u\)，删去 \(u\) 的连边后，图分为几种连通块：

  • \(u\)，贡献 \(2(n-1)\)，最后单独计算即可；
  • 不和 \(u\) 祖先相连的子树 \(v\)，它们满足 \(low[v]\ge dfn[u]\)；
  • 跨过 \(u\) 和其祖先相连的子树 \(v\)，它们满足 \(low[v]<dfn[u]\)，并且整体相连成一个连通块；

依次加入每个连通块，计量其与之前的连通块之间的贡献，最后再 \(\times 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
#include<iostream>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
const int M = 5e5 + 10;

struct Edge {
    int v, next;
} pool[2 * M];
int ne = 1, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n, m;
ll ans[N];

int sz[N];
int dfn[N], low[N], dt;
void tarjan(int u, int fe) {
    sz[u] = 1;
    low[u] = dfn[u] = ++dt;
    int sum = 0;
    for(int e = head[u]; e; e = pool[e].next) {
        if(e == fe) continue;
        int v = pool[e].v;
        if(!dfn[v]) {
            tarjan(v, e ^ 1);
            sz[u] += sz[v];
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) {
                ans[u] += (ll)sum * sz[v];
                sum += sz[v];
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    ans[u] += (ll)sum * (n - sum - 1);
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

    tarjan(1, 0);

    for(int i = 1; i <= n; i++) cout << (ans[i] + n - 1) * 2 << '\n';

    return 0;
}

P3225 [HNOI2012] 矿场搭建

给定一个无向图，现在一些节点可能坍塌；你需要设置一些关键点，使得任意的一个节点单独坍塌时，其他每一个节点都可以至少到达一个关键点；问最少设置多少个，以及最优时的方案数。

\(n,m\le 10^3\)

先进行点双缩点；注意到如果坍塌的节点不是割点，则图的连通性不会改变，我们只需要保证总是存在一个关键点即可。因此一个足够大的连通块中关键点至少有两个，一个仅包含一个节点的连通块只需一个。

否则，若删除了一个割点；一个 bcc 仍可能通过多个割点连接到多个其他 bcc。但是对于叶子 bcc，即仅存在一个割点的 bcc，当我们删除这个唯一的割点时，该 bcc（\(sz>1\)）就不与外面的部分连通了，因此其内部需要至少设置一个关键点。

对于孤立 bcc，其答案为 \(2\)；否则，其答案至少为 \(sz>1\) 的叶子 bcc 的数量。不难发现在每个叶子 bcc 内任意处（除割点）放置一个关键点，那么整个连通块就都是合法的。因为对于每一个非叶子 bcc，其至少存在两条分叉可以连接到两个不同的叶子。因此，对于包含两个及以上 bcc 的连通块，其答案为 \(sz>1\) 的叶子 bcc 的数量。

代码 
  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
#include<iostream>
#define ull unsigned long long
using namespace std;
const int N = 1e3 + 10;

struct Edge {
    int v, next;
} pool[2 * N];
int ne = 1, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n, m;

int dfn[N], low[N], dt;
int cut[N];
int col[N], bccCnt;
int deg[N], sz[N];

int ans1;
ull ans2;

void clear() {
    dt = bccCnt = 0;
    ne = 1;
    ans1 = 0;
    ans2 = 1;
    for(int i = 1; i <= n; i++) col[i] = dfn[i] = cut[i] = 0;
    for(int i = 1; i <= n; i++) deg[i] = sz[i] = 0;
    for(int i = 1; i <= n; i++) head[i] = 0;
}

void tarjan(int u, int fe) {
    low[u] = dfn[u] = ++dt;
    int chd = 0;
    for(int e = head[u]; e; e = pool[e].next) {
        if(e == fe) continue;
        int v = pool[e].v;
        if(!dfn[v]) {
            ++chd;
            tarjan(v, e ^ 1);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) cut[u] = 1;
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(!fe && chd <= 1) cut[u] = 0;
}

void dfs(int u) {
    col[u] = bccCnt;
    ++sz[bccCnt];
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(cut[v]) {
            if(col[v] != col[u]) ++deg[bccCnt], col[v] = col[u];
            continue;
        }
        if(!col[v]) {
            dfs(v);
        }
    }
}

int CaseNum;
int main() {

    while(true) {
        cin >> m;
        if(m == 0) break;
        n = m;
        clear();
        n = 0;
        for(int i = 1; i <= m; i++) {
            int u, v;
            cin >> u >> v;
            addEdge(u, v);
            addEdge(v, u);
            n = max(n, max(u, v));
        }
        tarjan(1, 0);
        for(int i = 1; i <= n; i++) {
            if(!col[i] && !cut[i]) {
                ++bccCnt;
                dfs(i);
            }
        }
        for(int i = 1; i <= bccCnt; i++) {
            if(deg[i] == 0) {
                if(sz[i] == 1) ans1 += 1;
                else ans1 += 2, ans2 *= (ull)sz[i] * (sz[i] - 1) / 2;
            } else if(deg[i] == 1) {
                ans1 += 1;
                ans2 *= sz[i];
            }
        }
        cout << "Case " << ++CaseNum << ": " << ans1 << ' ' << ans2 << '\n';
    }

    return 0;
}

P4082 [USACO17DEC] Push a Box P

给定一个推箱子的局面，多次询问是否能将箱子推到指定位置。

\(n,m\le 1500,\ q\le 5\times 10^4\)

我们注意到推箱子的动作是影响较大的，而箱子移动的方向取决于玩家的位置，而玩家在推箱子时一定只在箱子的四个方向。因此考虑一种搜索：设状态 \((i,j,0/1/2/3)\) 表示箱子位于 \((i,j)\)，玩家位于箱子的上下左右。

考虑如何转移，推动箱子的转移显然是平凡的；而玩家还可以从箱子的一个方向走动到另一个方向，考虑如何判定箱子的四个方向是否连通。注意到在没有箱子的情况下，箱子的四个方向一定是连通的（通过箱子占据的空位）；因此在存在箱子时，玩家要想从箱子的一侧移动到另一侧，那么在原图（没有箱子）上两点之间一定存在至少两条不交的路径。该条件显然是充要的。因此我们先求出原图的边双，然后就可以判断能否从箱子的一侧移动到另一侧。

代码 
  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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include<iostream>
using namespace std;
const int N = 1510 * 1510;
const int M = 2 * N;

int delta[4];

struct Edge {
    int v, next;
} pool[2 * M];
int ne = 1, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n, m, q;
int s, b;
int ban[N];

inline int g(int i, int j) { return (i - 1) * m + j; }
inline int gx(int p) { return (p - 1) / m + 1; }
inline int gy(int p) { return (p - 1) % m + 1; }

int bcc[N][5], cnt[N], bccCnt;

int dfn[N], low[N], dt;
int sta[N], top;
void tarjan(int u, int fe) {
    low[u] = dfn[u] = ++dt;
    sta[++top] = u;
    for(int e = head[u]; e; e = pool[e].next) {
        if(e == fe) continue;
        int v = pool[e].v;
        if(!dfn[v]) {
            tarjan(v, e ^ 1);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) {
                bcc[u][++cnt[u]] = ++bccCnt;
                while(sta[top + 1] != v) {
                    bcc[sta[top]][++cnt[sta[top]]] = bccCnt;
                    --top;
                }
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

inline bool in_bound(int p) { return 1 <= p && p <= n * m; }

inline bool in_bound(int p, int d) {
    if(!in_bound(p + delta[d])) return false;
    if(ban[p + delta[d]]) return false;
    if(d == 2 && p % m == 1) return false;
    if(d == 3 && p % m == 0) return false;
    return true;
}

bool check(int p, int d1, int d2) {
    if(!in_bound(p, d2)) return false;
    int u = p + delta[d1], v = p + delta[d2];
    for(int i = 1, j = 1; i <= cnt[u]; i++) {
        while(j <= cnt[v] && bcc[v][j] < bcc[u][i]) ++j;
        if(bcc[v][j] == bcc[u][i]) return true;
    }
    return false;
}

int valid[N];
void dfs(int u) {
    valid[u] = 1;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(valid[v] || v == b) continue;
        dfs(v);
    }
}

bool f[N][4];
struct Node {
    int p, d;
} que[4 * N];
int hd = 1, tl = 0;

inline void trans(int p, int d) {
    if(f[p][d]) return;
    f[p][d] = 1;
    que[++tl] = {p, d};
}

void bfs() {
    while(hd <= tl) {
        Node u = que[hd++];
        if(in_bound(u.p, u.d ^ 1)) trans(u.p + delta[u.d ^ 1], u.d);
        for(int d = 0; d < 4; d++) {
            if(d == u.d) continue;
            if(check(u.p, u.d, d)) trans(u.p, d);
        }
    }
}

int main() {

    cin >> n >> m >> q;
    delta[0] = -m; delta[1] = m; delta[2] = -1; delta[3] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            char c;
            cin >> c;
            if(c == '#') ban[g(i, j)] = 1;
            else if(c == 'A') s = g(i, j);
            else if(c == 'B') b = g(i, j);
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(ban[g(i, j)]) continue;
            if(i < n && !ban[g(i + 1, j)]) {
                addEdge(g(i, j), g(i + 1, j));
                addEdge(g(i + 1, j), g(i, j));
            }
            if(j < m && !ban[g(i, j + 1)]) {
                addEdge(g(i, j), g(i, j + 1));
                addEdge(g(i, j + 1), g(i, j));
            }
        }
    }

    int nn = n * m;
    for(int i = 1; i <= nn; i++) {
        if(!dfn[i]) tarjan(i, 0);
    }

    dfs(s);

    if(gx(b) > 1 && valid[b - m]) f[b][0] = 1, que[++tl] = {b, 0};
    if(gx(b) < n && valid[b + m]) f[b][1] = 1, que[++tl] = {b, 1};
    if(gy(b) > 1 && valid[b - 1]) f[b][2] = 1, que[++tl] = {b, 2};
    if(gy(b) < m && valid[b + 1]) f[b][3] = 1, que[++tl] = {b, 3};

    bfs();

    while(q--) {
        int x, y, p;
        cin >> x >> y;
        p = g(x, y);
        if(p == b) { cout << "YES\n"; continue; }
        cout << ((f[p][0] || f[p][1] || f[p][2] || f[p][3]) ? "YES\n" : "NO\n");
    }

    return 0;
}

BZOJ2841 Knights of the Round Table

给定一个 \(n\) 个点 \(m\) 条边的无向图，请你求出有多少个点不存在于一个 \(sz>1\) 的简单奇环中。

\(1\le n\le 10^5,\ 0\le m\le 3\times 10^5\)

引理

若一个边双连通图中存在一个简单奇环，则所有点都至少位于一个简单奇环中。

证明

考虑从最初的奇环扩展到全图。 不妨把这个奇环中的点取出来加入集合𝑆 ，则集合𝑆 满足 ● 所有点都在至少一个简单奇环上 ● 对任意 𝑢 , 𝑣 ∈ 𝑆 × 𝑆 ，𝑢 , 𝑣 之间同时存在长度为奇数的路径和长度为偶数的路径（路径 上全是𝑆 中的点） ● 那么不断重复如下操作 ● 在原图中去掉选出的所有点，原图分为若干连通块。此时对于任意连通块𝑋 ，其一定和在 集合内的至少两个点𝑢 , 𝑣 相连（若只与一个点相连，则这个点是割点，与点双矛盾） ● 选出𝑢 − 𝑋 − 𝑣 的任意一条路径（因为𝑋 连通所以这样的路径一定存在） ● 由于𝑢 , 𝑣 之间同时存在长度为奇数的路径和长度为偶数的路径，所以这条路径一定能成为奇环 的一部分 ● 同时对于路径上任意一点𝑥 和在𝑆 中的任意一点𝑦，𝑥 − 𝑢 − 𝑦也必然可奇可偶，那么就可以将 路径上的点全部加入𝑆 中 ● 最终所有点都会被加入𝑆，于是就能得出所有点都在至少一个简单奇环上

[err-tag]

于是我们对每个点双进行黑白染色，判定奇环即可。

代码 
  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
109
110
111
#include<iostream>
#include<vector>
using namespace std;
const int N = 1e5 + 10;
const int M = 3e5 + 10;

struct Edge {
    int v, next;
} pool[2 * M];
int ne = 1, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n, m, ans;

int dfn[N], low[N], dt;
int cut[N];

int d[N], col[N], bccCnt;
int ok[N], sz[N];

vector<int> bcc[N];
vector<int> inbcc[N];

int sta[N], top;

void tarjan(int u, int fe) {
    low[u] = dfn[u] = ++dt;
    sta[++top] = u;
    int chd = 0;
    for(int e = head[u]; e; e = pool[e].next) {
        if(e == fe) continue;
        int v = pool[e].v;
        if(!dfn[v]) {
            ++chd;
            tarjan(v, e ^ 1);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) {
                cut[u] = 1;
                bcc[++bccCnt].push_back(u);
                ++sz[bccCnt];
                while(sta[top + 1] != v) {
                    ++sz[bccCnt];
                    bcc[bccCnt].push_back(sta[top]);
                    --top;
                }
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(!fe && chd == 1) cut[u] = 0;
}

int nban[N], f[N];
void fill(int u, int c) {
    inbcc[u].push_back(c);
    if(!f[u]) f[u] = 1;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(!nban[v]) continue;
        if(f[v] && f[v] == f[u]) ok[c] = 1;
        if(!f[v]) {
            f[v] = -f[u];
            fill(v, c);
        }
    }
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) tarjan(i, 0);
    }

    for(int i = 1; i <= bccCnt; i++) {
        for(int j : bcc[i]) nban[j] = 1;
        fill(bcc[i][0], i);
        for(int j : bcc[i]) nban[j] = f[j] = 0;
    }

    for(int i = 1; i <= bccCnt; i++) {
        if(sz[i] == 1) ok[i] = 0;
    }

    for(int i = 1; i <= n; i++) {
        bool flag = false;
        for(int j : inbcc[i]) {
            if(ok[j]) {
                flag = true;
                break;
            }
        }
        ans += !flag;
    }

    cout << ans << '\n';

    return 0;
}