1971. Find if Path Exists in Graph
经典的题目，给定 undirected graph 上的 s, t 两点
问两点是否连通
用 DFS 或是 union find 其实都可以
不过看讨论区提到 union find 的复杂度是 O(E α(V))
其中 α() 是 inverse Ackermann function
才发现我好像还真的不知道 union find 的复杂度
找到一篇介绍文
https://codeforces.com/blog/entry/98275
先 po 出来提醒自己之后找个时间看
不过讲个可能不是很多人知道的东西
即使把题目改成 directed graph
这题的空间复杂度也可以在 O(log^2 n) 内
这个算法来自一个蛮有名的定理
Savitch's theorem
首先，令 n 是节点的数目
所以 s 跟 t 之间存在路径若且唯若 s 跟 t 之间存在长度 <= n 的路径
（最长就是把每个点都走过）
令 Path(u, v, k) 表示 u 跟 v 之间存在长度 <= 2^k 的路径
而 u 跟 v 之间存在 <= 2^k 的路径有两种可能
1. u 跟 v 之间直接有边
2. 存在中心点 x 使得 Path(u, x, k - 1) 且 Path(x, v, k - 1)
（一个 <= 2^k 长的路径一定能切成两半，且任一边长度 <= 2^{k-1}）
最后检查 Path(s, t, log(n)) 就可以了
这个递回的深度最多是 log(n)，
乘上存 index 的大小 log(n) 就是 O(log^2 n)
但因为在每层都要遍历所有节点，所以很显然并不是一个多项式算法
就完全不用提拿来实际用了
查了一下，发现如果是 undirected graph 的话还可以在 O(log n) 空间内完成
这个结果还是 2004 年才出来的 好新喔