Tarjan 算法寻找有向图的强连通分量

在图论中，一个有向图被成为是强连通的（strongly connected）当且仅当每一对不相同结点 u 和 v 间既存在从 u 到 v 的路径也存在从 v 到 u 的路径。有向图的极大强连通子图（这里指点数极大）被称为强连通分量（strongly connected component）。

比如说这个有向图中，点 $1, 2, 4, 5, 6, 7, 8$ 和相应边组成的子图就是一个强连通分量，另外点 $3, 9$ 单独构成强连通分量。

Tarjan 算法是由 Robert Tarjan 提出的用于寻找有向图的强连通分量的算法。它可以在$\mathcal O(|V|+|E|)$的时间内得出结果。

Tarjan 算法主要是利用 DFS 来寻找强连通分量的。在介绍该算法之前，我们先来介绍一下搜索树。先前那个有向图的搜索树是这样的：

有向图的搜索树主要有 4 种边（这张图只有 3 种），其中用实线画出来的是树边（tree edge），每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。用长虚线画出来的是反祖边（back edge），也被叫做回边。用短虚线画出来的是横叉边（cross edge），它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点并不是当前节点的祖先时形成的。除此之外，像从结点1到结点6这样的边叫做前向边（forward edge），它是在搜索的时候遇到子树中的结点的时候形成的。

反演魔术：反演原理及二项式反演

首先我来说说什么是反演（inversion），对于一个数列$\{f_n\}$来说，如果我们知道另外一个数列$\{g_n\}$，满足如下条件 \[ g_n = \sum_{i=0}^n a_{ni}f_i \] 反演过程就是利用 $g_0, g_1, \cdots, g_n$ 来表示出 $f_n$ \[ f_n = \sum_{i = 0}^n b_{ni}g_i \] 本质上来说，反演其实是一个解线性方程组的过程，但是你观察后发现，这个矩阵实际上是一个三角矩阵，那必然存在着快捷的方法。对于使得这两个反演公式成立的这些系数应该满足什么条件呢？我们现在就来探讨一番！ 我们首先讨论一下在什么情况下能够比较容易建立反演公式，之后介绍二项式反演以及它的两个应用，其中一个是错位排列问题

Catalan 数列及其应用

卡特兰数（Catalan number）是组合数学中一个重要的计数数列，在很多看似毫不相关地方都能见到它的身影

这篇文章介绍卡特兰数的几个应用以及它的推导过程，从组合推理和生成函数两个方面来推导出 Catalan 数的公式

带限制条件的路径总数

首先我们来看一个问题：

在一个平面直角坐标系中，只能往右或往上走一个单位长度，问有多少种不同的路径可以从左下角 $(1, 1)$ 走到右上角 $(n, n)$，并且要求路径不能经过直线 $y = x$ 上方的点，下图中的路径都是合法的（图片来源 Wikipedia）

如果没有限制条件，那么从左下角走到右上角一共有 $2n$ 步，有 $n$ 步是往右，另外 $n$ 步是往上，那么路径方案数就是 $2n$ 步中选择 $n$ 步往右，一共有 ${2n} \choose {n}$ （即 $C_{2n}^n$）种方案

那么我们考虑一下这里面有多少种方案是不合法的

首先对于每一种不合法的方案，它的路径一定与 $y = x + 1$ 有交。我们找到它与 $y = x + 1$ 的第一个交点，然后将这个点后面部分的路径关于 $y = x + 1$ 做一个对称。由于原来路径到达 $(n, n)$，新的对称之后的路径就会到达 $(n - 1, n + 1)$。这样我们把每一种不合法方案都对应到了一条从 $(1, 1)$ 到 $(n - 1, n + 1)$ 的路径，现在再来看是否每一条这样的路径都能对应到一种不合法方案，如果是，那么这就建立了一个一一映射的关系，也就是它们的方案总数相同。这是肯定的，因为每一条这样的路径必定与 $y = x + 1$ 有交，那么对称回去，就得到一条不合法方案

由于从 $(1, 1)$ 到 $(n - 1, n + 1)$ 的路径有 ${n - 1 + n + 1} \choose {n - 1}$ 条，那么合法的方案就是

\[C_n = { {2n} \choose {n} } - { {2n} \choose {n - 1} } = \frac{1}{n + 1} { {2n} \choose {n} }\]

我们把这个方案数记为 $C_n$，这就是著名的 Catalan 数

Codeforces 上的一些组合计数问题

Codeforces 15E. Triangles

Problem：给出一个有规律的金字塔（如图），黑色的边是可以走路径，要求求出包含 $H$ 点的简单回路（不经过一个顶点两次）的条数，并且这个回路围住的部分不可以包含灰色的三角形，答案对 $10^9+9$ 取模，其中 $n \leq 10^6$，并且一定是一个偶数

Example：当 $n = 2$ 时，一共有 $10$ 种方案，其中 $5$ 种是这样，另外的是顺时针顺序地走

Solution：首先第 $1$ 层是最特殊的，因为这里没有灰色的三角形，然后注意到灰色的部分把整个金字塔分成了左部和右部

路径现在可以分成三个部分

• 在第一层移动，这一共 $10$ 种（见样例）
• 进入左部或右部后直接回到 $H$
• 进入左部（右部）后经过 $E$ 点进入右部（左部）

对于第二种情况，在第一层的部分走法可以是（只有逆时针部分，实际上有 $8$ 种）

• $A \rightarrow B \rightarrow D \rightarrow \text{LeftPart} \rightarrow E \rightarrow C \rightarrow A$
• $A \rightarrow B \rightarrow D \rightarrow \text{LeftPart} \rightarrow E \rightarrow F \rightarrow C \rightarrow A$
• $A \rightarrow B \rightarrow E \rightarrow \text{RightPart} \rightarrow F \rightarrow C \rightarrow A$
• $A \rightarrow B \rightarrow D \rightarrow E \rightarrow \text{RightPart} \rightarrow F \rightarrow C \rightarrow A$

对于第三种情况，在第一层（原来图中的两层现在算一层，也就是下面的 $n$ 是题目中 $n$ 的 $\frac{1}{2}$）的部分走法有 $2$ 种，左部到右部和右部到左部

现在要统计的就是在左部和右部内有多少种方案，因为左部右部对称，所以答案是一样的，我们来考虑左部

用 $S_n$ 表示在有 $n$ 层的金字塔中，走左部的方案数，因为走进左部后每一层都会遇到凹进去的部分，这部分只要枚举一下走了多远可以统计出第 $n$ 层一共有 $2\sum_{i=1}^{n-2} 2^i + 1 = 2^n - 3$ 这么多的情况

然后要走到第 $n$ 层后就是 $\prod_{i=2}^{n} (2^i - 3)$ 种情况，然后走回去的路径有 $4$ 种选择，因此

\[ S_n = \sum_{i=2}^{n} 4\prod_{j=2}^i (2^j - 3) \]

答案是 $2S_n^2 + 8S_n + 10$

牛顿迭代法在多项式运算的应用

总算是快把 FFT 和生成函数的各种东西补了好多，膜拜策爷的论文和 Picks 的博客！

这篇文章大概就是说如何用牛顿迭代法来解满足 $G(F(z)) \equiv 0 \pmod {z^n}$ 的 $F(z)$

然后这东西可以比较方便地计算 $\sqrt{A(z)}$、$e^{A(z)}$，也就是多项式开根、求指数对数之类鬼畜的东西，在生成函数计数中十分有用

顺便一提，这里说的“多项式”实际上你可以直接理解为生成函数或者形式幂级数

平面图转对偶图及点定位

平面图（planar graph）就是一个可以在平面上画出来的图，并且所有的边只在顶点处相交。平面图的对偶图（dual graph）是将这个平面的每个区域看成点，原图每一条边所属的两个相邻的区域对应在对偶图中的点有连边

比如下面这张图（来源于 Wikipedia）

蓝色的部分就是一个平面图，红色的就是它的对偶图

平面图的点定位（point location）就是找出一个点属于这个图的哪个区域

这篇文章介绍如何将一个平面图转换为其对偶图，和基于扫描线的离线的点定位算法

BZOJ-3456. 城市规划

题目要求求出有 $n (n \leq 130000)$ 个点的有标号简单连通无向图的个数，答案 $\bmod 1004535809$ $(479 \times 2^{21} + 1)$，是个质数

比如三个点的情况

题目链接：BZOJ-3456