LeetCode 2924. Find Champion II in F#

URL

https://leetcode.com/problems/find-champion-ii/description/?envType=daily-question&envId=2024-11-26

Code

https://github.com/syohex/dotnet-study/blob/master/fsharp/leetcode/challenge/202411/find_champion2/main.fsx

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

            toGraph t acc

    let rec dfs node graph cache =
        match Map.tryFind node cache with
        | Some(v) -> v, cache
        | None ->
            match Map.tryFind node graph with
            | None -> 1, Map.add node 1 cache
            | Some(v) ->
                let ret, cache =
                    v
                    |> List.fold
                        (fun (acc, cache) n ->
                            match Map.tryFind n cache with
                            | Some _ -> acc, cache
                            | None ->
                                let ret, cache = dfs n graph cache
                                acc + ret, cache)
                        (1, cache)

                ret, Map.add node ret cache

    let rec findChampion' i n graph =
        if i >= n then
            -1
        else
            let ret, _ = dfs i graph Map.empty
            if ret = n then i else findChampion' (i + 1) n graph

    let graph = toGraph edges Map.empty
    findChampion' 0 n graph