UC Berkeley CS 170 2023年秋季 作业 4

观察：对于顶点 \(v\)，\n\[ s[v] = \sum_{c \text{ 是 } v \text{ 的子节点}} s[c] + (\text{距离 } v \text{ 恰好为 } K \text{ 的后代数量}) \tag{1} \]\n\n算法流程如下。将所有 \(s[v]\) 值初始化为 0，并从根节点开始 DFS。在算法的每一步，我们将当前节点的祖先维护在一个单独的数组中。为了确保数组中只包含当前 DFS 路径上的顶点，我们仅在真正访问某个顶点时才将其加入数组（下标等于当前深度）。由于一条路径最多包含 \(n\) 个顶点，该数组长度最多为 \(n\)。\n\n处理节点 \(v\) 时，首先定位到它在数组中的第 \(K\) 个祖先，记为 \(a\)。然后将 \(s[a]\) 加 1，以计入 \(v\) 的贡献。当处理完 \(v\) 的一个子节点 \(c\) 后，将 \(s[c]\) 加到 \(s[v]\) 上。\n\n复杂度分析：由于我们在 DFS 的每一步只执行常数个额外操作，算法仍为 \(O(|V|)\)。\n\n正确性证明：对于顶点 \(v\) 及其子节点 \(c\)，每个被计入 \(s[c]\) 的节点也应被计入 \(s[v]\)，因为这些节点到 \(v\) 的距离只会增加。此外，恰好距离 \(v\) 为 \(K\) 的节点不会被计入任一子节点（它们到对应子节点的距离小于 \(K\)）。因此，这些节点会在访问 \(v\) 的第 \(K\) 代后代时被计入，并使 \(s[v]\) 加 1。注意，当完成对节点 \(v\) 的处理时，\(s[v]\) 的值已正确，可供其父节点使用。

主算法思路：构造有向图 \(G = (V, E)\)，顶点代表冰屋，边代表单向道路。一个可靠冰屋等价于属于某个有向环的顶点。因此我们的目标是统计 \(G\) 中属于某个环的顶点数量。\n\n首先运行 Kosaraju 算法计算 \(G\) 的所有强连通分量（SCC），并稍作修改使其同时计算每个 SCC 的顶点数量。然后，所求顶点集由所有位于大小至少为 2 的 SCC 中的顶点 \(v \in V\) 构成。\n\n正确性证明：任何 SCC \(S \subseteq G\) 都是一个子图，其中所有顶点互相可达。因此，大小至少为 2 的 SCC 中的顶点按定义构成一个环：任一顶点 \(v\) 可到达另一顶点 \(u \in S\)，而 \(u\) 又能返回 \(v\)。\n\n复杂度分析：Kosaraju 算法耗时 \(O(n+m)\)，遍历所有顶点确定目标集合耗时 \(O(n)\)（假设在 Kosaraju 过程中我们构建了一个以顶点为键、SCC 大小为值的哈希表）。因此总运行时间为 \(O(n+m) + O(n) \in O(n+m)\)。

这是一个有向图，每个节点代表一个物种，从 \(x\) 到 \(y\) 的边表示 \(y\) 直接源自 \(x\)。可将该图视为以 Mew 为根的有向树。\n\n在该图上运行 DFS，存储每个节点的先序编号（pre-number）和后序编号（post-number）。当程序收到查询时，通过检查 \(\text{pre}[b] < \text{pre}[a] < \text{post}[a]\) 判断 \(a\) 是否源自 \(b\)，或通过检查 \(\text{pre}[a] < \text{pre}[b] < \text{post}[a]\) 判断 \(b\) 是否源自 \(a\)，否则得出结论：\(a\) 和 \(b\) 有共同祖先但彼此不源自对方。\n\nDFS 耗时 \(O(p)\)，但属于预处理。查询涉及索引两个数组并比较，耗时 \(O(1)\)。

将每个盒子视为有向图中的一个节点，从 \(a\) 到 \(b\) 的边表示 \(a\) 能放入 \(b\)。由于 Falexa 只给出反方向的边（即告诉 Bob 哪些盒子能放入 \(b\)），我们需要先构造图再将其边反转，这可在关于图线性的时间内完成。该图是一个有向无环图（DAG）：如果盒子 \(a\) 能放入 \(b\) 且盒子 \(c\) 能放入 \(a\)，则 \(b\) 不可能放入 \(c\)。我们将进入节点 \(a\) 的入边权重设为对应盒子的重量 \(w\)。从最小的盒子 \(x\) 开始运行 DFS 对该 DAG 进行线性化（拓扑排序），然后按照拓扑序遍历 DAG 的顶点，通过建立在到之前节点路径基础上的方式计算每条新最短路径，从而在 \(x\) 到任意其他盒子之间找到最短路径。

方向一：若存在一条访问所有顶点的有向路径 \(p\)，则 \(G\) 是半连通的。对任意两个顶点 \(A\) 和 \(B\)，考虑 \(p\) 上 \(A\) 与 \(B\) 之间的子路径。若 \(A\) 在 \(p\) 中出现在 \(B\) 之前，则该子路径从 \(A\) 指向 \(B\)；否则从 \(B\) 指向 \(A\)。无论哪种情况，\(A\) 和 \(B\) 都是半连通的，这对 \(G\) 中所有顶点对 \((A,B)\) 都成立。\n\n方向二：若 \(G\) 是半连通的，则存在一条访问所有顶点的有向路径。考虑 \(G\) 的一个拓扑序 \(v_1, v_2, \ldots, v_n\)。对任意一对连续顶点 \(v_i, v_{i+1}\)，由半连通性知存在从 \(v_i\) 到 \(v_{i+1}\) 的路径或从 \(v_{i+1}\) 到 \(v_i\) 的路径。但拓扑序中不存在从后向前顶点的边。因此存在从 \(v_i\) 到 \(v_{i+1}\) 的路径。该路径不能访问 \(G\) 中任何其他顶点，因为路径不能从拓扑序中靠后的顶点走向靠前的顶点。因此从 \(v_i\) 到 \(v_{i+1}\) 的路径必为单条边 \(v_i \to v_{i+1}\)。该边存在于拓扑序中任意一对连续顶点之间，故存在一条从 \(v_1\) 到 \(v_n\) 且访问所有顶点的路径。

假设存在一个同时包含 \(x\) 和 \(\neg x\) 的 SCC。注意图中的边都是必要的蕴含（implication）。因此，若 \(x\) 和 \(\neg x\) 在同一分量中，则存在一条蕴含链等价于 \(x \Rightarrow \neg x\)，以及另一条不同的链等价于 \(\neg x \Rightarrow x\)，即子句集中存在矛盾。

任取一个汇点 SCC，并赋值使得该分量中的所有文字为 True。由于我们构造图的方式，存在一个对应的源点 SCC（source SCC），其中包含该分量中所有文字的否定。移除这一对源/汇分量，重复此过程直到图为空。由于我们以逆拓扑序将分量设为 True，因此不存在从 True 文字到 False 文字的蕴含。由于没有文字和其否定在同一 SCC 中，我们永远不会试图将一个变量同时设为 True 和 False。因此这产生了一个满足所有子句的赋值。

设 \(\phi\) 是作用于 \(n\) 个文字 \(x_1, \ldots, x_n\) 上的公式。构造一个具有 \(2n\) 个顶点的图，代表所有文字及其否定。对 \(\phi\) 的每个子句 \((a \lor b)\)，添加边 \(\neg a \Rightarrow b\) 和 \(\neg b \Rightarrow a\)。使用强连通分量算法，对每个 \(i\) 检查是否存在同时包含 \(x_i\) 和 \(\neg x_i\) 的 SCC。若找到任何这样的分量，报告不可满足（unsatisfiable）；否则报告可满足（satisfiable）。\n\n（注意：一个常见错误是，只要图中存在从 \(x_i\) 到 \(\neg x_i\) 的路径——即使没有从 \(\neg x_i\) 回到 \(x_i\) 的路径——就报告不可满足。即使存在一系列蕴含组合得到 \(x_i \Rightarrow \neg x_i\)，除非我们也知道 \(\neg x_i \Rightarrow x_i\)，否则仍可将 \(x_i\) 设为 False 并可能满足所有子句。例如，考虑 2-SAT 公式 \((\neg a \lor b) \land (\neg a \lor \neg b)\)：这些子句等价于 \(a \Rightarrow b\)、\(b \Rightarrow \neg a\) 等，其中 \(a \Rightarrow b \Rightarrow \neg a\) 给出 \(a \Rightarrow \neg a\)，但该公式仍容易满足（令 \(a = \text{False}\) 即可）。）

任务 1.1 解答：\npython\nvisited = set()\nprev = [-1] * len(adj_list)\ndef explore(u):\n visited.add(u)\n for v in adj_list[u]:\n if v not in visited:\n prev[v] = u\n explore(v)\nfor start in range(len(adj_list)):\n if start not in visited:\n prev[start] = start\n explore(start)\nreturn prev\n\n\n任务 1.2 解答：\npython\ntime = 1\npre = []\npost = []\nvisited = set()\ndef explore(u):\n nonlocal time\n visited.add(u)\n pre.append((u, time))\n time += 1\n for v in adj_list[u]:\n if v not in visited:\n explore(v)\n post.append((u, time))\n time += 1\nfor i in range(len(adj_list)):\n if i not in visited:\n explore(i)\nreturn pre, post\n\n\n任务 1.3 解答：\npython\nprev = dfs(adj_list)\npreorder, postorder = get_pre_post(adj_list)\npre, post = {}, {}\nfor u, time in preorder:\n pre[u] = time\nfor u, time in postorder:\n post[u] = time\nfor u in range(len(adj_list)):\n for v in adj_list[u]:\n edge = (u, v)\n if pre[u] < pre[v] < post[v] < post[u]:\n if prev[v] == u:\n edges_lookup['tree'].add(edge)\n else:\n edges_lookup['forward'].add(edge)\n elif pre[v] < pre[u] < post[u] < post[v]:\n edges_lookup['back'].add(edge)\n else:\n edges_lookup['cross'].add(edge)\nreturn edges_lookup\n\n\n任务 2.1 解答：\npython\nreversed_adj_list = [[] for i in range(len(adj_list))]\nfor u in range(len(adj_list)):\n for v in adj_list[u]:\n reversed_adj_list[v].append(u)\nreturn reversed_adj_list\n\n\n任务 2.2 解答：\npython\nreversed_graph = reverse_graph(adj_list)\n_, postorder = get_pre_post(reversed_graph)\nvisited = set()\nscc_list = []\ndef explore(u):\n visited.add(u)\n curr_set.append(u)\n for v in adj_list[u]:\n if v not in visited:\n explore(v)\nfor u, _ in postorder[::-1]:\n if u not in visited:\n curr_set = []\n explore(u)\n scc_list.append(set(curr_set))\nreturn scc_list\n