DAG（有向无环图）归档 – Charles Wu的博客

洛谷题库 P2272 [ZJOI2007]最大半连通子图题解与思路重现

有感而发，今晚一定先写篇题解。~~这可是我AC的第一道紫题！~~

题目中说半连通子图指的是对于图 $G(V, E)$ ， $\forall u, v \in V$ 有 $u \to v$ 或者 $v \to u$ 。当时我对于“或”的理解是异或，也就是二者不能同时存在。

——那这题基本没法做啊？比如我们作一次DFS，搜索的时候光是找到一条横叉边，就已经让人头疼怎么处理；更别说还要判环，还要找“最大”的半连通子图。

但有一点是可以确定的——当图中可以将环处理掉时，“半连通子图”将会是一条链。易知对于链上的节点 $u, v$ (u是v的祖先)，都有 $u \to v$ 。