给定只读的无向图 \(G=(V,E)\)，在仅有 \(O(\log |V|)\) 个比特的额外空间内判定 \(G\) 是否为森林。
将边 \((u,v)\) 拆成两条有向边，考察如下访问边的过程：
以任意边开始，若当前边为 \((u,v)\)，则下一条边访问 \((v,w)\)，其中 \((v,w)\) 是 \(v\) 的出边中紧邻着 \((v,u)\) 的后一条边。
此过程事实上构造了 \(2|E|\) 条边之间的置换，现在声称 \(G\) 是森林等价于 \(\forall (u,v)\in E,(u,v),(v,u)\) 在相同置换环上，并且任意置换环是“合法括号序列”（也即，在环 \(C\) 上，\(\forall (u,v),(a,b)\in C,(a,b),(b,a)\) 在 \((u,v),(v,u)\) 的同侧）
前推后是容易的，后推前首先通过第一个条件，可以确定相同连通块内的边必然在同一个环上，然后只需在每个环上不断找到 \((u,v),(v,u)\) 相邻的边并删除，通过删除过程可构造出唯一的树。
验证两个条件都可以在 \(O(\log |V|)\) 个比特的空间内完成，具体来说只需枚举 \((u,v),(a,b)\)，记录 \(O(1)\) 个编号即可。
注意仅保留第一个条件不对，对 \(K_4\) 构造一下就能得到反例。
事实上判定无向图可达性也可以在 \(O(\log |V|)\) 个比特内完成，很酷！