URL

Minimum Time to Collect All Apples in a Tree - LeetCode

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/problems/1443/main.fsx

let edgesToGraph (edges: (int * int) list) =
    let rec edgesToGraph' edges acc =
        match edges with
        | [] -> acc
        | (s, e) :: t ->
            let acc' =
                match Map.tryFind s acc with
                | None -> Map.add s [ e ] acc
                | Some(v) -> Map.add s (e :: v) acc

            let acc'' =
                match Map.tryFind e acc with
                | None -> Map.add e [ s ] acc'
                | Some(v) -> Map.add e (s :: v) acc'

            edgesToGraph' t acc''

    edgesToGraph' edges Map.empty

let minTime (n: int) (edges: (int * int) list) (hasApple: Set<int>) : int =
    let rec minTime' node parent graph =
        Map.find node graph
        |> List.fold
            (fun acc next ->
                if next = parent then
                    acc
                else
                    let childTime = minTime' next node graph

                    if childTime > 0 || (Set.contains next hasApple) then
                        acc + childTime + 2
                    else
                        acc)
            0

    let graph = edgesToGraph edges
    minTime' 0 -1 graph