海淀二模21题个人试做

1. DFS树，tarjan，和支配树
   1. 从DFS树的性质谈起
      1. 无向图
      2. 有向图
   2. Tarjan算法
      1. e-BCC(边双联通分量)
      2. v-BCC(点双联通分量)
      3. SCC(强连通分量)
   3. 支配树
      1. 定义
      2. 性质
      3. 求法
      4. 代码
   4. 例题
   5. Reference

DFS树，tarjan，和支配树

从DFS树的性质谈起

无论是有向图或者是无向图，通过一次如下的DFS，我们都可以将该图的边分为四类：树边，前向边(祖先连向子孙)，后向/返祖边(子孙连向祖先)，横叉边(其他)。

function visit(u):
     mark u as visited;
     for each vertex v among the neighbours of u:
         if v is not visited:
             mark the edge uv;
             visit(v);

无向图

显然在无向图中，前向/后向边是没有区别的。

Lemma 1: 对于无向图的dfs树，不存在横叉边。

证明:

考虑dfs过程中会遍历所有相邻未被访问的边，对于横叉边，假设先被访问到，则暂未被访问，会通过访问。

有向图

然而在有向图中，横叉边可以存在，但是与上面类似，横叉边必然满足，否则访问后必然访问。

由此，另一性质

Lemma 2: 经过一条树边/前向边,dfs序减小，经过一条横叉边/后向边，dfs序必然增大。

Tarjan算法

e-BCC(边双联通分量)

由上文

v-BCC(点双联通分量)

SCC(强连通分量)

支配树

定义

现在有一个有向图和起点 ，对于点 ，如果任意一条从 的路径都要经过 ，换种说法就是如果删去 就无法从 到 ，那么 就是 的支配点。所有支配 的点的集合就是点 的支配集。

性质

支配关系显然具有偏序性(即支配，支配,则支配)，且对于连通图，显然支配任何点，由此，支配关系是一个。

除此之外

求法

代码

例题

Reference

1. CommonAnts - DFS树,Tarjan强连通分量和支配树 - bilibili（上）（下）
2. qwq_123 - 支配树 - 博客园
3. -is-this-fft-‘s blog - [Tutorial] The DFS tree and its applications: how I found out I really didn’t understand bridges - CodeForces

---

欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 pmt2018@hotmail.com