Add Leetcode 1971. Find if Path Exists in Graph attempt

[dnahol]

Attempted Wed 7/26/23 7:22 pm during Hacker Dojo DS&A event.

There is a bug. Find it.

/**

• @param {number} n
• @param {number[][]} edges
• @param {number} source
• @param {number} destination
• @return {boolean}

start at source dfs or bfs? mark visited

dfs is easier to code, can use both

return true if destination found else return false

*/ var validPath = function(n, edges, source, destination) {

//convert to adjacency list

/*
[[0,1],[1,2],[2,0]]

0 [[1,2], 1 [0,2],
2 [1,0]] */

let adj = edges.reduce((acc, edge)=>{
    let v1 = edge[0]
    let v2 = edge[1]
    if(acc[v1] === undefined) acc[v1] = []
    if(acc[v2] === undefined) acc[v2] = []
    acc[v2].push(v1)
    return acc
}, [])

let seen = new Set([]);

return dfs(adj, source, destination, seen) 

};

var dfs = function(adj, source, destination, seen) { if(source === destination) return true

seen.add(source)
//traverse
let result = false
for(let v of adj[source]) {
    if(!seen.has(v)) result = result || dfs(adj, v, destination)
}
return result

}

[dnahol]

// bug 1: forgot to push v2 onto v1 array

let adj = edges.reduce((acc, edge)=>{ let v1 = edge[0] let v2 = edge[1] if(acc[v1] === undefined) acc[v1] = [] if(acc[v2] === undefined) acc[v2] = [] acc[v2].push(v1) return acc }, [])

// should be: acc[v1].push(v2)

// bugs 2 & 3: 2 typos in if statement inside dfs traverse loop

for(let v of adj[source]) { if(!seen.has(v)) result = result || dfs(adj, v, destination) }

// should be: if(!seen.has(v)) result = true else dfs(adj, v, destination)