Categorygithub.com/szhou12/leetcode-goleetcode1971-Find-if-Path-Exists-in-Graph
package
0.0.0-20241220224003-b7cf03a90b2b
Repository: https://github.com/szhou12/leetcode-go.git
Documentation: pkg.go.dev
Overview
Dependencies
0
Dependents
0

# README

1971. Find if Path Exists in Graph

Solution idea

DFS 暴力解 - 会超时！！！

Union Find

  • 把连通的vertex都添加到一个集合中
  • 再判断 source 和 destination 是否有用一个根节点 (ie. 在同一个集合中)
    • 如果有同一个根节点，说明有路径
    • 否则，没有

Time complexity = $O(n)$ where $n=$ # of edges

代码随想录-1971. 寻找图中是否存在路径