Cut-point-algorithm

Cut-point-algorithm

Charles Lv7
  2023-01-12 17:41 2023-01-12 17:41 Created   2023-07-30 10:52:51 2023-07-30 10:52:51 Updated      1.7k Words  7 Mins  

Cut-point-algorithm

割点和割边

既然已经写了有关缩点的博客，趁热打铁出一片关于割点的博客(没错，用到的算法还是Tarjan），其实Tarjan算法有好几个，但我感觉用起来都差不多，也就不细分了。废话少说，开始正篇。
本文重点以割点为例展开介绍，割边区别不大(就类似邻接表和链式前向星差不多)，但代码都会展示。

定义

割点：当在一个连通的图中，去除某个点，使得该图不再连通，而被去除的点就是该图的割点。
割边（桥）：如割点一样，在一个连通的图中，去除某条边，使得该图不再连通，而被去除的条边就是该图的割边，也称桥。

理论上如何判断割点和割边

首先，由于是Tarjan算法，所以不出意料我们需要引入一个时间轴(dfn)和连接轴(low）。

我们可以在脑海里想象一个图，1–2 ，2–3 ，3–4 ，4–2（无向图），我们从一端开始，假设它的编号为1，我们每次到达一个结点，都初始化dfn 和 low 当前时间。 (比如：我们从1结点开始 ，时间也从1开始，那么结点1的dfn 和 low都为1；结点2的dfn 和 low就为2……) 当结点来到4时，结点4指向的是2，此时，结点4的low 则改变为2；说明产生了回退边（该结点的孩子指向了当前结点之前）由于我们是通过DFS实现在回溯的同时更新前方已访问过的结点的low。

这些步骤结束之后，开始直观判断割点，如果该结点的dfn < 孩子的low，说明改结点是割点 。 否则，说明孩子与比自己当前位置还前的结点有连接。所以，就算去除自己，孩子还是会通过另外一条路径与整个图相连。但值得注意的是开始的端点结点，它的时间最早，所以不管它的孩子的low值怎么变化 它的dfn 都小于孩子的low, 显然并不是所有的端点都是割点 ，对于这种情况我们用孩子数量的办法，当端点的孩子数量 多于1时说明是割点。

割边判断方法一样，当前结点的u的dfn < 孩子结点v的low时，且不需要判断开始点不需要另外判断，则割边为：u–v;

实现

割点判断

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
int cut[N], cnt;
int dfn[N], low[N], id;
void tarjan(int step, int root) {//当前结点和双亲结点
    low[step] = dfn[step] = ++id;//初始化时间轴和连接轴为当前时间。
    int child = 0;//该结点的孩子,主要用于判断头结点是否为割点。
    for (int k = g.head[step]; k != -1; k = g.e[k].link) {
        int v = g.e[k].to;
        if (!dfn[v]) {//如果该结点未被访问
            tarjan(v, root);
            low[step] = min(low[step], low[v]);
            //放在tarjan()的后面，所以在此结点后的结点都已更新连接轴的值
            if (low[v] >= dfn[step] && step != root) {
                //如果当前结点（不是头结点）时间轴的值小于等于孩子的连接轴的值，则当前结点为割点
                cut[step] = 1;
            }
            if (step == root) {
                child++;
            }
        }
        low[step] = min(low[step], dfn[v]); //更新step连接轴的值
    }
    if (child >= 2 && step == root) {
        //如果step == root时不能用上述程序实现,通过孩子数量来确定是否为割点
        cut[step] = 1;
    }
}
割点数求解

在割点的求解代码中没有对割点数目进行计算，只是进行了cut[]标记，所以如果需要割点是数目，需要将所有结点遍历一遍。

1
2
3
4
5
for (int i = 1; i <= n; i++) {
    if (cut[i]) {
        cnt++;
    }
}

割边判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int dfn[N], low[N], id;
stack<Edge> s;//用一个栈来存储割边,所以Tarjan后s.size()就是割点数。
void tarjan(int step, int root) {
    low[step] = dfn[step] = ++id;
    int child = 0;//孩子个数，主要用于根结点判断割点
    for (int k = g.head[step]; k != -1; k = g.e[k].link) {
        int v = g.e[k].to;
        if (!dfn[v]) {
            child++;//这里孩子数量变化和割点有差异
            tarjan(v, root);
            low[step] = min(low[step], low[v]);
            if (low[v] > dfn[step]) {//判断割点与这里不同；
            //注意：若这里的判断条件改为 num < low 就成为了判断割边的条件
                edge* tail = new Edge;
                tail->from = step;
                tail->to = v;
                s.push(*tail);
            }
            
        }
        low[step] = min(low[step], dfn[v]);
    }
}

模板题

【模板】割点（割顶）

【模板】割点（割顶）

题目背景

割点

题目描述

给出一个 $n$ 个点，$m$ 条边的无向图，求图的割点。

输入格式

第一行输入两个正整数 $n,m$。

下面 $m$ 行每行输入两个正整数 $x,y$ 表示 $x$ 到 $y$ 有一条边。

输出格式

第一行输出割点个数。

第二行按照节点编号从小到大输出节点，用空格隔开。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
6 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6
样例输出 #1
1
2
1 
5

提示

对于全部数据，$1\leq n \le 2\times 10^4$，$1\leq m \le 1 \times 10^5$。

点的编号均大于 $0$ 小于等于 $n$。

tarjan图不一定联通。

AC代码

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
#include <bits/stdc++.h>
using namespace std;
#define M 200007
#define N 20007
#define INF 0x3f3f3f3f
#define mod 99999997
#define ll long long
#define db double
#define pii pair<int, int>
int n, m;
typedef struct edge {
    int from, to, link;
} Edge;
typedef struct node {
    int id;
} Node;
typedef struct graph {
    int head[N];
    int node_num = 0;
    Node p[N];
    int edge_num = 0;
    Edge e[M];
} Graph;
Graph g;
void add_edge(int from, int to) {
    g.e[++g.edge_num].to = to;
    g.e[g.edge_num].from = from;
    g.e[g.edge_num].link = g.head[from];
    g.head[from] = g.edge_num;
}
int cut[N], cnt;
int dfn[N], low[N], id;
void tarjan(int step, int root) {
    low[step] = dfn[step] = ++id;
    int child = 0;
    for (int k = g.head[step]; k != -1; k = g.e[k].link) {
        int v = g.e[k].to;
        if (!dfn[v]) {
            tarjan(v, root);
            low[step] = min(low[step], low[v]);
            if (low[v] >= dfn[step] && step != root) {
                cut[step] = 1;
            }
            if (step == root) {
                child++;
            }
        }
        low[step] = min(low[step], dfn[v]);
    }
    if (child >= 2 && step == root) {
        cut[step] = 1;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    memset(g.head, -1, sizeof(g.head));
    cin >> n >> m;
    int u, v;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i, i);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (cut[i]) {
            cnt++;
        }
    }
    cout << cnt << endl;
    for (int i = 1; i <= n; i++) {
        if (cut[i]) {
            cout << i << " ";
        }
    }
    return 0;
}
  • Title: Cut-point-algorithm
  • Author: Charles
  • Created at : 2023-01-12 17:00:41
  • Updated at : 2023-07-30 10:52:51
  • Link: https://charles2530.github.io/2023/01/12/cut-point-algorithm/
  • License: This work is licensed under CC BY-NC-SA 4.0.
recommend_articles
Trie tree Trie tree database-theory-9 database-theory-9 lab_discussion_1 lab_discussion_1
recommend_articles
Trie tree Trie tree database-theory-9 database-theory-9
Comments
On this page
Cut-point-algorithm
  1. Cut-point-algorithm
    1. 割点和割边
      1. 定义
      2. 理论上如何判断割点和割边
      3. 实现
        1. 割点判断
          1. 割点数求解
        2. 割边判断
    2. 模板题
      1. 题目描述
      2. 输入格式
      3. 输出格式
      4. 样例 #1
        1. 样例输出 #1
      5. 提示
    3. AC代码