无向图的连通性

一些定义

在无向连通图 $G$ 上进行如下定义:

割点:若删掉某点 $P$ 后,$G$ 分裂成两个或两个以上的子图,则称 $P$ 为 $G$ 的割点。

割点集合:如果有一个顶点集合,删除这个顶点集合以及与该点集中的顶点相关联的边以后,原图分成多于一个连通块,则称这个点集为 $G$ 的割点集合。

点连通度:最小割点集合的大小称为无向图 $G$ 的点连通度。

割边(桥):若删掉某条边 $e$ 后,$G$ 分裂成两个或两个以上的子图,则称 $e$ 为 $G$ 的割边(桥)。

割边集合:如果有一个边集合,删除这个边集后,原图分成多于一个连通块,则称这个边集为割边集合。

边连通度:最小割边集合的大小称为无向图 $G$ 的边连通度。

点双连通图:点连通度大于 $1$ 的图称为点双连通图(没有割点)。

边双连通图:边连通度大于 $1$ 的图称为边双连通图(没有割边)。

(点/边)双连通分量:无向图的极大(点/边)双连通子图称为(点/边)双连通分量。


Tarjan 算法

Tarjan 基于对图的深度优先搜索,对每个节点引入了两个值:

$dfn[u]$:节点 $u$ 的时间戳,记录点 $u$ 是 $DFS$ 过程中第几个访问的节点。

$low[u]:$ 记录节点 $u$ 或 $u$ 的子树 不经过搜索树上的边能够到达的时间戳最小的节点。

维护方法

对于每一条与 $u$ 相连的边 $(u,v)$

若在搜索树上 $v$ 是 $u$ 的子节点,则更新 $low[u] = min ( low[u], low[v] )$

若 $(u,v)$ 不是搜索树上的边,则更新 $low[u] = min(low[u], dfn[v])$

求割点

对于搜索树上的一条边 $(u,v)$,其中 $u$ 是 $v$ 的父节点,若 $low[v] >= dfn[u]$,则 $u$ 为割点。

$low[v] >= dfn[u]$ 说明从 $v$ 及 $v$ 的子树的点 到以 $u$ 为根的子树之外的点必须要经过点 $u$,因此 $u$ 是割点。

注意: 如果根只有一个孩子,那么它不是割点。

vector<int> G[maxn];
int dfs_clock, dfn[maxn];
bool iscut[maxn];
int dfs(int u, int fa) {
    int lowu = dfn[u] = ++dfs_clock;
    int child = 0;
    for (auto &v : G[u]) {
        if (!dfn[v]) {
            child++;
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            if (lowv >= dfn[u]) iscut[u] = true;
        } else if (dfn[v] < dfn[u] && v != fa)
            lowu = min(lowu, dfn[v]);
    }
    if (fa < 0 && child == 1) iscut[u] = false;  // root
    return lowu;
}

点双联通分量

其他定义:对于一个无向连通图,如果任意两点至少存在两条点不重复路径,则称这个图为点双连通的。

可以在求割点的过程中维护一个栈,从而求出每个点双连通分量。

建立一个栈,存储 DFS 过程中访问的节点, 初次访问一个点时把该点入栈。

如果边 $(u,v)$ 满足 $low[v] >= dfn[u]$,即满足了 $u$ 是割点的判断条件,那么把点从栈顶依次取出,直至取出了点 $v$,取出的这些点和点 $u$ 一起组成了一个点双连通分量。

割点可能属于多个点双连通分量,其余点和每条边属于且仅属于一个点双连通分量。因此在从栈中取出节点时,要把 $u$ 留在占中。

整个 $DFS$ 结束后,栈中还剩余的节点构成一个点双联通分量。

vector<int> G[maxn], bcc[maxn];
int bcc_cnt, dfs_clock;
int dfn[maxn], iscut[maxn], bccno[maxn];
stack<pii> stk;
int dfs(int u) {
    int lowu = dfn[u] = ++dfs_clock;
    int child = 0;
    for (auto &v : G[u]) {
        pii e = {u, v};
        if (!dfn[v]) {
            stk.push(e);
            child++;
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            if (lowv >= dfn[u]) {  // u为割点
                iscut[u] = true;
                bcc_cnt++;
                bcc[bcc_cnt].clear();  //注意!bcc从1开始编号
                for (;;) {
                    pii x = stk.top();
                    stk.pop();
                    if (bccno[x.first] != bcc_cnt)
                        bcc[bcc_cnt].push_back(x.first), bcc[x.first] = bcc_cnt;
                    if (bccno[x.second] != bcc_cnt)
                        bcc[bcc_cnt].push_back(x.second),
                            bcc[x.second] = bcc_cnt;
                    if (x.first == u && x.second == v) break;
                }
            }
        } else if (dfn[v] < dfn[u] && v != fa) {
            stk.push(e);
            lowu = min(lowu, dfn[v]);
        }
    }
    if (fa < 0 && child == 1) iscut[u] = 0;
    return lowu;
}
//割点的bccno无意义
void solve(int n) {
    //调用结束后stack保证为空,所以不用清空
    memset(iscut, 0, sizeof(iscut));
    memset(bccno, 0, sizeof(bccno));
    memset(dfn, 0, sizeof(dfn));
    dfs_clock = bcc_cnt = 0;
    for (int i = 0; i < n; i++)
        if (!dfn[i]) dfs(i, -1);
}

注意对每个割点或者割边来说,判定定理可能不止一次成立,所以不要边判定边输出。

割边

对于一条搜索树上的边 $(u,v)$,其中 $u$ 是 $v$ 的父节点,若 $low[v] > dfn[u]$,则 $(u,v)$ 是桥。

$low[v]$ 表示 $v$ 和 $v$ 的子树不经过搜索树上的边能够到达的时间戳的最小的节点。

$low[v] > dfn[u]$ 说明从以 $v$ 为根的子树到子树之外的必须要经过边 $(u,v)$,因此 $(u,v)$ 是桥。

可以像求割点一样,当 $v$ 回溯至 $u$ 后,判断上述不等式是否成立。

另一种判断方法:当递归 $v$ 结束时,如果 $low[v] == dfn[v]$ 说明 $v$ 和 $v$ 的父节点之间的边是桥。

注意:在有重边的图上求桥,需要对重边加以区分。需要记录 $(u,fa)$ 的数量,若大于 $1$ 说明有重边,则要设置 $low[u] = dfn[fa]$。

vector<pii> G[maxn];  // first: 下一个点, second: 该边的编号
int dfs_clock, dfn[maxn];
bool iscut[N];  // N: 边数

int dfs(int u, int fa) {
    int lowu = dfn[u] = ++dfs_clock;
    // int father = 0;
    for (auto &V : G[u]) {
        int v = V.first;
        int id = V.second;  // 边的编号
        // if(v == fa) father++;
        if (!dfn[v]) {
            int lowv = dfs(v, u);
            lowu = min(lowv, lowu);
            if (lowv > dfn[u]) iscut[id] = true;
        } else if (dfn[v] < dfn[u] && v != fa)
            lowu = min(lowu, dfn[v]);
    }
    // if(father > 1) return dfn[fa];
    return lowu;
}

边双联通分量

其他定义:对于一个无向连通图,如果任意两点至少存在两条边不重复路径,则称该图为边双连通的。

边双连通分量的求法非常简单,只需在求出所有的桥后,把桥删除。

此时原图分成了若干个连通块,每个连通块就是一个边双连通分量。

桥不属于任何一个边双连通分量

其余的边和每个顶点都属于且仅属于一个边双连通分量。

vector<int> G[maxn];
int bcc_cnt, dfs_clock;
int dfn[maxn], bccno[maxn];
stack<int> stk;
int dfs(int u, int fa) {
    int lowu = dfn[u] = ++dfs_clock;
    stk.push(u);
    bool flag = false;  // 有重边
    for (auto &v : G[u]) {
        if (v == fa && !flag) {
            flag = true;
            continue;
        }
        if (!dfn[v]) {
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
        } else
            lowu = min(lowu, dfn[v]);
    }
    if (lowu == dfn[u]) {
        bcc_cnt++;  // 编号从1开始
        while (!stk.empty()) {
            int v = stk.top();
            bccno[v] = bcc_cnt;
            if (u == v) break;
        }
    }
}
边双连通分量的构造

任意给定一个无向连通图,最少添加多少条边可以把它变为双连通图?

求出所有的桥和边双连通分量,把每个双连通分量缩成一个点。

此时的图只包含缩点后的双连通分量 和 桥边,是一棵无根树。

统计树中度数为 $1$ 的节点的个数 $cnt$ 。把树变为边双连通图,至少需要添加 $\lceil \frac{cnt}{2} \rceil$ 条边。

构造方法

设缩点后的叶子为 $v_1, v_2, ... , v_n$,让 $v_i$ 与 $v_{i + \lfloor \frac{n}{2} \rfloor}$ 连边即可。

如果相连的两个节点的 $LCA$ 不是根的话,必然会留下一些桥(根到 $LCA$ 的路径上都是桥)。

有向图连通性

强连通分量

若在一张有向图中,各个点互相可达,则称此图强连通。

最大强连通子图又称强连通分量。

实际问题中,强连通分量往往会被看成一个点来处理(缩点)。

vector<int> G[maxn];
int scc, dfs_clock, top;  // scc: 强连通分量的数量
bool instack[maxn];
int dfn[maxn], low[maxn], belong[maxn], Stack[maxn];
// int num[maxn];      // 每个强连通分量的数量。 1 ~ scc
// int maps[maxn];      //缩点之后 每个点对应的新点的标号
void Tarjan(int u) {
    dfn[u] = low[u] = ++dfs_clock;
    instack[u] = true;
    Stack[top++] = u;
    for (auto &v : G[u]) {
        if (!dfn[v]) {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (instack[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        ++scc;
        int cnt = 0;
        int now;
        while (top > 0) {
            now = Stack[--top];
            instack[now] = false;
            belong[now] = u;
            ++cnt;
            if (now == u) {
                // num[scc] = cnt;
                // maps[u] = scc;
                break;
            }
        }
    }
}
void solve(int n) {
    memset(instack, 0, sizeof(instack));
    memset(dfn, 0, sizeof(dfn));
    scc = dfs_clock = top = 0;
    for (int i = 1; i <= n; i++) {  // 点的标号从1开始
        if (!dfn[i]) Tarjan(i);
    }
}

有向图的必经结点(割点)(支配树)

给定有向图 $G$(可能有环)和图中的一个点 $s$,对于 $G$ 中的任意一个点 $t$,求从 $s$ 到 $t$ 的路径上(可能有很多条)必须经过的点集。

支配树:$(G,s)$ 的支配树是一棵根为 $s$ 的有向树,从 $s$ 出发可以到达 $G$ 中的所有点。
$x$ 的必经节点集合 $dom(x)$ 就是支配树上 根 $s$ 到 $x$ 路径上的点集。

一些概念

必经点(dom)(割点)

若从 $s$ 到 $t$ 的路径一定经过点 $x$,则称 $x$ 是从 $s$ 到 $t$ 的必经点(割点),记为 $x\quad dom\quad t$。

从 $s$ 出发到达 $t$ 的所有必经点集合为 $dom(t)$,即 $dom(t) = \{x | x\quad dom\quad y\}$.

最近必经点(idom)

节点 $t$ 的必经点集合 $dom(t)$ 中 $dfn$ 值最大的点 $x$ 是距离 $t$ 最近的必经点,称 $x$ 为 $t$ 的最近必经节点。

最近必经点是唯一的,因此可以记 $x = idom(t)$。

半必经点(semi)

在搜索树 $T$ 上,点 $t$ 的祖先中通过非树边可以到达 $t$ 的且 $dfn$ 最小的祖先 $x$,称为 $t$ 的半必经点。半必经点也是唯一的,因此可以记为 $x = semi(t)$。

半必经点定理

对于 $G$ 中的一点 $t$,考虑所有 $x \in pre(t)$(前驱),定义一个临时变量 $tmp = INF$。

若 $dfn[x] < dfn[t]$,则 $(x,t)$ 为树边或前向边,此时 $tmp = min(tmp, dfn[x])$。

若 $dfn[x] > dfn[t]$,则 $(x,t)$ 为横叉边或后向边,此时 $x$ 的祖先中所有满足 $dfn[z] > dfn[t]$ 的,有 $tmp = min(tmp, dfn[semi[z]])$。

$semi[t] = id[tmp]$,即在上述所有可能情况中取 $dfn$ 值最小的一种,就是 $t$ 的半必经点。

必经点定理

对于 $G$ 中的一点 $x$,考虑搜索树 $T$ 中 $semi(x)$ 到 $x$ 的路径上除端点之外的点构成的集合 $path$。

设 $y$ 为 $path$ 中半必经点的时间戳最小的节点。

若 $semi(x) = semi(y)$,则 $idom(x) = semi(x)$。

若 $semi(x) \neq semi(y)$,则 $idom(x) = idom(y)$

Lengauer-Tarjan 算法:

通过DFS构建搜索树,并计算出每个节点的时间戳。

根据半必经点定理,按照时间戳从大到小的顺序计算每个节点的半必经节点。

根据必经点定理,按照时间戳从小到大的顺序,把半必经节点 $\neq$ 必经节点的点进行修正。

// dom[i]:(支配树)编号为i的点所支配的最近节点
// idom[i]:编号为i的点的最近必经节点
// semi[i]:编号为i的点的半必经节点
// id[i]:dfn为i的点的编号
// best[i]:编号为i的点的祖先中dfn最小的点的编号
// pre[i]:编号为i的点的前驱
// suc[i]:编号为i的点的后继
// son[i]:编号为i的点的儿子
struct DomiTree {
  int dfs_clock;
  int dfn[maxn], id[maxn], fa[maxn];
  int semi[maxn], best[maxn], idom[maxn];
  vector<int> pre[maxn], dom[maxn], suc[maxn], son[maxn];

  void init(int n) {
    for (int i = 0; i <= n; i++) {
      pre[i].clear(), dom[i].clear(), suc[i].clear(), son[i].clear();
      fa[i] = best[i] = idom[i] = semi[i] = i, dfn[i] = 0;
    }
    dfs_clock = 0;
  }
  void addedge(int u, int v) {
    // u -> v
    pre[v].push_back(u);
    suc[u].push_back(v);
  }
  void build(int s) {
    dfs(s);
    tarjan();
  }
  void dfs(int u) {
    dfn[u] = ++dfs_clock;
    id[dfs_clock] = u;
    for (auto &v : suc[u]) {
      if (dfn[v]) continue;
      dfs(v);
      son[u].push_back(v);
    }
  }
  inline int Min(int x, int y) { return dfn[semi[x]] < dfn[semi[y]] ? x : y; }

  int find(int u) {
    if (u == fa[u]) return u;
    int v = find(fa[u]);
    best[u] = Min(best[fa[u]], best[u]);
    return fa[u] = v;
  }
  void tarjan() {
    for (int i = dfs_clock; i > 0; i--) {
      int k = id[i];
      for (auto v : pre[k]) {
        if (dfn[v] == 0) continue;
        if (dfn[v] < dfn[k] && dfn[v] < dfn[semi[k]]) semi[k] = v;
        if (dfn[v] >= dfn[k]) {
          find(v);
          semi[k] = semi[Min(best[v], k)];
        }
      }
      if (k != semi[k]) dom[semi[k]].push_back(k);
      for (auto &v : dom[k]) {
        find(v);
        if (semi[best[v]] == k)
          idom[v] = k;
        else
          idom[v] = best[v];
      }
      dom[k].clear();
      for (auto &v : son[k]) fa[v] = k;
    }
    for (int i = 2; i <= dfs_clock; i++) {
      int k = id[i];
      if (idom[k] != semi[k]) idom[k] = idom[idom[k]];
      if (k != idom[k]) dom[idom[k]].push_back(k);
    }
  }
} dt;

有向图的必经边(割边)

给定有向图 $G$(可能有环)和图中的一个点 $s$,对于 $G$ 中的任意一个点 $t$,求 $s$ 到 $t$ 路径上(可能有多条)的必经边的集合。

无环图做法

求 $s$ 到每个点的路径数 $Scnt$,$t$ 到每个点的路径数 $Tcnt$。

若边 $(u,v)$ 满足 $Scnt[u] \times Tcnt[v] = Scnt[t]$,那么 $(u,v)$ 是从 $s$ 到 $t$ 的必经边。

可以对几个大质数取模做上述计算。

有环图做法

在 $(u,v)$ 中间加一个点 $w$,然后利用 $Lengauer-Tarjan$ 算法求有向图割点,若 $w$ 是割点,那么 $(u,v)$ 是割边。

最后修改:2020 年 07 月 30 日 10 : 19 PM