leetcode-go/leetcode/medium/399.evaluate-division.go

type pair struct {
	key   string
	ratio float64
}

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
	m, n := len(values), len(queries)
	route := make(map[string][]pair)
	for i := 0; i < m; i++ {
		a, b := equations[i][0], equations[i][1]
		if a == b {
			if _, ok := route[a]; !ok {
				route[a] = make([]pair, 0)
			}
			continue
		}
		route[a] = append(route[a], pair{b, values[i]})
		route[b] = append(route[b], pair{a, 1.0 / values[i]})
	}
	ans := make([]float64, n)
	for i := 0; i < n; i++ {
		visited := make(map[string]bool)
		if ratio := dfs(route, queries[i][0], queries[i][1], &visited); ratio == 0.0 {
			ans[i] = -1.0
		} else {
			ans[i] = ratio
		}
	}
	return ans
}

func dfs(route map[string][]pair, a, b string, visited *map[string]bool) float64 {
	if a == b {
		if _, ok := route[a]; ok {
			return 1.0
		} else {
			return 0.0
		}
	}
	(*visited)[a] = true
	adj := route[a]
	for i := range adj {
		if (*visited)[adj[i].key] {
			continue
		}
		ratio := adj[i].ratio * dfs(route, adj[i].key, b, visited)
		if ratio != 0.0 {
			return ratio
		}
	}
	return 0.0
}