Problem#
給你一個雙向圖有 $n$ 個點 $m$ 條邊，從 $0$ 到 $n-1$，問你能不能從 src 走到 dst
- $1 \le n \le 2e5$
- $0 \le m \le 2e5$
- 沒有重複的邊 or 自環
想法#
disjoint set $\approx \mathcal{O}(1)$
- 時間複雜度: $\mathcal{O}(m)$ m = number of edges
- 空間複雜度: $\mathcal{O}(n)$
AC Code#
- disjoint set
- DFS
賞析#
https://haogroot.com/2021/01/29/union_find-leetcode/
https://zh.wikipedia.org/zh-tw/并查集
https://hackmd.io/SSUEUC2_SWW6CBPvgT6yiA
https://leetcode.com/problems/find-if-path-exists-in-graph/solutions/2715942/find-if-path-exists-in-graph/
心得#
太久沒有寫 disjoint set 直接忘記了= =