From eac7aabdc0b1b0ee2ba0051e1c3eeb4ffd8d62cc Mon Sep 17 00:00:00 2001
From: Trisolaris HD <36555123+TrisolarisHD@users.noreply.github.com>
Date: Mon, 29 Apr 2019 17:29:02 +0800
Subject: [PATCH] Update bridge.md

---
 docs/graph/bridge.md | 126 ++++++++++++++++++++++++++-------------------------
 1 file changed, 64 insertions(+), 62 deletions(-)

diff --git a/docs/graph/bridge.md b/docs/graph/bridge.md
index 76006cb3..9e7b094c 100644
--- a/docs/graph/bridge.md
+++ b/docs/graph/bridge.md
@@ -4,7 +4,7 @@
 
 ## 割点
 
-> 如果在一个图中，如果把一个点删除，那么这个图的连通分支数增加，那么这个点就是割点（割顶）。
+> 对于一个无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点（又称割顶）。
 
 ### 如何实现？
 
@@ -48,81 +48,83 @@ low[u] = min(low[u], num[v]);
 
 ### Code
 
-```cpp
-/*
-洛谷 P3388 【模板】割点（割顶）
-*/
-#include <bits/stdc++.h>
-using namespace std;
-int n, m;  // n：点数 m：边数
-int num[100001], low[100001], inde, res;
-// num：记录每个点的时间戳
-// low：能不经过父亲到达最小的编号，inde：时间戳，res：答案数量
-bool vis[100001], flag[100001];  // flag: 答案 vis：标记是否重复
-vector<int> edge[100001];        // 存图用的
-void Tarjan(int u, int father)  // u 当前点的编号，father 自己爸爸的编号
-{
-  vis[u] = true;             // 标记
-  low[u] = num[u] = ++inde;  // 打上时间戳
-  int child = 0;             // 每一个点儿子数量
-  for (auto v : edge[u])     // 访问这个点的所有邻居 （C++11）
-  {
-    if (!vis[v]) {
-      child++;                       // 多了一个儿子
-      Tarjan(v, u);                  // 继续
-      low[u] = min(low[u], low[v]);  // 更新能到的最小节点编号
-      if (father != u && low[v] >= num[u] &&
-          !flag
-              [u])  // 主要代码
-                    // 如果不是自己，且不通过父亲返回的最小点符合割点的要求，并且没有被标记过
-                    // 要求即为：删了父亲连不上去了，即为最多连到父亲
+??? " 例题代码 "
+
+    ```cpp
+    /*
+    洛谷 P3388 【模板】割点（割顶）
+    */
+    #include <bits/stdc++.h>
+    using namespace std;
+    int n, m;  // n：点数 m：边数
+    int num[100001], low[100001], inde, res;
+    // num：记录每个点的时间戳
+    // low：能不经过父亲到达最小的编号，inde：时间戳，res：答案数量
+    bool vis[100001], flag[100001];  // flag: 答案 vis：标记是否重复
+    vector<int> edge[100001];        // 存图用的
+    void Tarjan(int u, int father)  // u 当前点的编号，father 自己爸爸的编号
+    {
+      vis[u] = true;             // 标记
+      low[u] = num[u] = ++inde;  // 打上时间戳
+      int child = 0;             // 每一个点儿子数量
+      for (auto v : edge[u])     // 访问这个点的所有邻居 （C++11）
+      {
+        if (!vis[v]) {
+          child++;                       // 多了一个儿子
+          Tarjan(v, u);                  // 继续
+          low[u] = min(low[u], low[v]);  // 更新能到的最小节点编号
+          if (father != u && low[v] >= num[u] &&
+              !flag
+                  [u])  // 主要代码
+                        // 如果不是自己，且不通过父亲返回的最小点符合割点的要求，并且没有被标记过
+                        // 要求即为：删了父亲连不上去了，即为最多连到父亲
+          {
+            flag[u] = true;
+            res++;  // 记录答案
+          }
+        } else if (v != father)
+          low[u] =
+              min(low[u], num[v]);  // 如果这个点不是自己，更新能到的最小节点编号
+      }
+      if (father == u && child >= 2 &&
+          !flag[u])  // 主要代码，自己的话需要 2 个儿子才可以
       {
         flag[u] = true;
         res++;  // 记录答案
       }
-    } else if (v != father)
-      low[u] =
-          min(low[u], num[v]);  // 如果这个点不是自己，更新能到的最小节点编号
-  }
-  if (father == u && child >= 2 &&
-      !flag[u])  // 主要代码，自己的话需要 2 个儿子才可以
-  {
-    flag[u] = true;
-    res++;  // 记录答案
-  }
-}
-int main() {
-  cin >> n >> m;                // 读入数据
-  for (int i = 1; i <= m; i++)  // 注意点是从 1 开始的
-  {
-    int x, y;
-    cin >> x >> y;
-    edge[x].push_back(y);
-    edge[y].push_back(x);
-  }                             // 使用 vector 存图
-  for (int i = 1; i <= n; i++)  // 因为 Tarjan 图不一定连通
-    if (!vis[i]) {
-      inde = 0;      // 时间戳初始为 0
-      Tarjan(i, i);  // 从第 i 个点开始，父亲为自己
     }
-  cout << res << endl;
-  for (int i = 1; i <= n; i++)
-    if (flag[i]) cout << i << " ";  // 输出结果
-  for (int i = 1; i <= n; i++) cout << low[i] << endl;
-  return 0;
-}
-```
+    int main() {
+      cin >> n >> m;                // 读入数据
+      for (int i = 1; i <= m; i++)  // 注意点是从 1 开始的
+      {
+        int x, y;
+        cin >> x >> y;
+        edge[x].push_back(y);
+        edge[y].push_back(x);
+      }                             // 使用 vector 存图
+      for (int i = 1; i <= n; i++)  // 因为 Tarjan 图不一定连通
+        if (!vis[i]) {
+          inde = 0;      // 时间戳初始为 0
+          Tarjan(i, i);  // 从第 i 个点开始，父亲为自己
+        }
+      cout << res << endl;
+      for (int i = 1; i <= n; i++)
+        if (flag[i]) cout << i << " ";  // 输出结果
+      for (int i = 1; i <= n; i++) cout << low[i] << endl;
+      return 0;
+    }
+    ```
 
 ## 割边
 
 和割点差不多，还叫做割桥。
 
-> 无向图中，去掉一条边，图中的连通分量数增加，则这条边，称为桥或者割边。
+> 对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。
 
 ### 实现
 
 和割点差不多，只要改一处： $low_v>num_u$ 就可以了，而且不需要考虑根节点的问题。
 
-割边是和是不是根节点没关系的，原来我们求割点的时候是指点 $v$ 是不可能不经过父节点 $u$ 为回到祖先节点（包括父节点），所以顶点 $u$ 是割点。如果 $low_v==num_u$ 表示还可以回到父节点，如果顶点 $v$ 不能回到祖先也没有另外一条回到父亲的路，那么 $u-v$ 这条边就是割边。
+割边是和是不是根节点没关系的，原来我们求割点的时候是指点 $v$ 是不可能不经过父节点 $u$ 为回到祖先节点（包括父节点），所以顶点 $u$ 是割点。如果 $low_v=num_u$ 表示还可以回到父节点，如果顶点 $v$ 不能回到祖先也没有另外一条回到父亲的路，那么 $u-v$ 这条边就是割边。
 
  Tarjan 算法还有许多用途，常用的例如求强连通分量，缩点，还有求 2-SAT 的用途等。
-- 
2.11.0