推 dannyko: 大師 12/20 06:53
推 peter6666712: 大師 12/20 07:27
推 Rushia: 太早 12/20 08:24
→ Rushia: 不對這昨天的題 12/20 08:25
推 PyTorch: 大師 12/20 09:07
推 pandix: 大師 12/20 11:07
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 年才出來的 好新喔
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1671484768.A.F94.html