Leetcode Note: Go - Find if Path Exists in Graph

Find if Path Exists in Graph - LeetCode
https://leetcode.com/problems/find-if-path-exists-in-graph/

  • Go 言語で取り組んだメモ

回答

Golang solution with image for explanation - Find if Path Exists in Graph - LeetCode
https://leetcode.com/problems/find-if-path-exists-in-graph/solutions/1415893/golang-solution-with-image-for-explanation/

func validPath(n int, edges [][]int, start int, end int) bool {
    m := make(map[int] []int)
    
    for _, edge := range edges {
        m[edge[0]] = append(m[edge[0]], edge[1])
        m[edge[1]] = append(m[edge[1]], edge[0])
    }
    
    alreadyDid := make(map[int] bool) // preventing infinite loops
    stack := []int{ start }
    
    for len(stack) != 0 {
        pop := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        
        if pop == end {
            return true
        }
        
        if !alreadyDid[pop] {
            alreadyDid[pop] = true
            stack = append(stack, m[pop]...)
        }
    }
    
    return false
}