2020-2021:teams:i_dont_know_png:nikkukun:cycle_space
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:i_dont_know_png:nikkukun:cycle_space [2020/05/12 16:52] nikkukun 创建 |
2020-2021:teams:i_dont_know_png:nikkukun:cycle_space [2020/05/12 16:52] (当前版本) nikkukun 修改格式 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ====== 环空间 ====== | ====== 环空间 ====== | ||
| - | 如果两个环可以异或相消，则一个图中的所有简单环，可以由某个钦定的点 $u$ 为始末点的所有简单环组合得到。实现可以用 DFS，记录第一次访问到某个点时的路径异或值 $dis_u$，则每次访问到已经经过的点时，只需要把当前的异或值和 $dis_u$ 异或一下就成了一个环。显然，这样找到的环的个数是 $\mathcal{O}(V + E)$ 的。 | + | 如果两个环可以异或相消，则一个图中的所有简单环，可以由某个钦定的点 $u$ 为始末点的所有简单环组合得到。实现可以用 DFS，记录第一次访问到某个点时的路径异或值 $\mathrm{dis}_u$，则每次访问到已经经过的点时，只需要把当前的异或值和 $\mathrm{dis}_u$ 异或一下就成了一个环。显然，这样找到的环的个数是 $\mathcal{O}(V + E)$ 的。 |
| 仔细想想，上面的过程实际就是随便找了一棵生成树（DFS 树），然后把所有非树边和两点最短路径相连，就构成了一个基本环。如果相连的是一个树边也无所谓，反正绕成一圈之后就完全没贡献了。 | 仔细想想，上面的过程实际就是随便找了一棵生成树（DFS 树），然后把所有非树边和两点最短路径相连，就构成了一个基本环。如果相连的是一个树边也无所谓，反正绕成一圈之后就完全没贡献了。 | ||
2020-2021/teams/i_dont_know_png/nikkukun/cycle_space.1589273540.txt.gz · 最后更改: 2020/05/12 16:52 由 nikkukun
