企业官网建设流程全解析

m C_{n-1}\)，\(A_{i,j}\) 表示一条连接 \(R_i,C_j\) 的边。在此基础上可以想到两种建图方法：

Method 1

建无向图，\(A_{i,j}\) 作为边权。

不难发现原限制是 \(0/1\) 边各自的边导出子图为连通图的充分不必要条件。\(2n-1\) 条边恰好是一个生成树，但是发现生成树不好构造，我们就卡住了。

Method 2

建有向图，\(A_{i,j}\) 表示方向，转化成二分竞赛图：

• 若 \(A_{i,j}=1\)：建边 \(R_i \to C_j\)
• 若 \(A_{i,j}=0\)：建边 \(C_j \to R_i\)

那么原条件等价于原图中没有四元环。进一步地，可以归纳证明这样的二分图一定无环。即：二分竞赛图中，无四元环等价于整张图无环。

现在问题转化成了如何用 \(2n-1\) 条边表示这样一个有向无环二分图。我们只需要知道任意两点间的拓扑序大小关系。

注意到，若当前图中存在 \(k\) 个入度为 \(0\) 的点，在不取完这 \(k\) 个点之前，是不可能产生新的入度为 \(0\) 的点的。这样一层层剥掉入度为 \(0\) 的点，就将图分成了若干层。显然，同层内一定无边。那么我们只需要知道每个点所在的层。

显然，除第一层外，每个点必须有来自前一层的入边。对于每个点我们随便记录一条这样的边，会得到一个外向有向树森林，其中根为第一层的点，点在树中的深度就是它所在的层号。然后就做完了。

Code