Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者fxfxxxfxx (愛麗絲)時間3年前 (2022/12/20 05:19)推噓5(5推 0噓 1→)

留言6則, 5人參與討論串143/719 (看更多)

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

推

dannyko

12/20 06:53, 3年前 , 1^F

12/20 06:53, 1^F

推

peter6666712

12/20 07:27, 3年前 , 2^F

12/20 07:27, 2^F

推

Rushia

12/20 08:24, 3年前 , 3^F

12/20 08:24, 3^F