1971.寻找图中是否存在路径.md

1971.寻找图中是否存在路径

/*
 * @lc app=leetcode.cn id=1971 lang=typescript
 *
 * [1971] 寻找图中是否存在路径
 */

// @lc code=start
function validPath(n: number, edges: number[][], source: number, destination: number): boolean {}
// @lc code=end

解法 1: BFS

function validPath(n: number, edges: number[][], source: number, destination: number): boolean {
  const h: number[] = new Array(n).fill(-1),
    e: number[] = [],
    ne: number[] = []
  const add = (i: number, j: number) => (e.push(j), ne.push(h[i]), (h[i] = ne.length - 1))
  for (let [u, v] of edges) {
    add(u, v)
    add(v, u)
  }
  const queue = [source],
    vis: number[] = []
  vis[source] = 1
  for (let u of queue) {
    if (u === destination) return true
    for (let i = h[u]; ~i; i = ne[i]) {
      const v = e[i]
      if (vis[v]) continue
      vis[v] = 1
      queue.push(v)
    }
  }
  return false
}

Case

test.each([
  {
    input: {
      n: 3,
      edges: [
        [0, 1],
        [1, 2],
        [2, 0],
      ],
      source: 0,
      destination: 2,
    },
    output: true,
  },
  {
    input: {
      n: 6,
      edges: [
        [0, 1],
        [0, 2],
        [3, 5],
        [5, 4],
        [4, 3],
      ],
      source: 0,
      destination: 5,
    },
    output: false,
  },
])(
  'input: n = $input.n, edges = $input.edges, source = $input.source, destination = $input.destination',
  ({ input: { n, edges, source, destination }, output }) => {
    expect(validPath(n, edges, source, destination)).toEqual(output)
  },
)