# LeetCode 1192. Critical Connections in a Network in F#

Shohei Yoshida
·May 18, 2022·

## URL

leetcode.com/problems/critical-connections-..

## Code

github.com/syohex/dotnet-study/blob/master/..

``````open System

let toGraph (conns: (int * int) list) : Map<int, int list> =
conns
|> List.fold
(fun acc (src, dest) ->
let acc' =
match Map.tryFind src acc with
| None -> Map.add src [ dest ] acc
| Some (v) -> Map.add src (dest :: v) acc

match Map.tryFind dest acc' with
| None -> Map.add dest [ src ] acc'
| Some (v) -> Map.add dest (src :: v) acc')
Map.empty

let criticalConnections (n: int) (connections: (int * int) list) : (int * int) list =
let rec f
(node: int)
(parent: int)
(rank: int)
(graph: Map<int, int list>)
(visited: Map<int, int>)
(acc: (int * int) list)
: (int * Map<int, int> * (int * int) list) =
match Map.tryFind node visited with
| Some (v) -> v, visited, acc
| None ->
let visited' = Map.add node rank visited

Map.find node graph
|> List.fold
(fun (minRank, visited, acc) next ->
if next = parent then
minRank, visited, acc
else
let rank', visited', acc' = f next node (rank + 1) graph visited acc

if rank' = rank + 1 then
Math.Min(minRank, rank'), visited', ((node, next) :: acc')
else
Math.Min(minRank, rank'), visited', acc')
(rank, visited', acc)

let graph = toGraph connections
let _, _, ret = f 0 -1 0 graph Map.empty []
ret
``````