Первое решение

Вот так выглядел первый вариант решения, который смог победить бота. Несмотря на то, что с задачей этот код справляется, меня он не устраивал. Если бы писал бота для игры, то поддержка такого кода вызывала бы только нехорошие мысли об авторе. Поэтому я задумал рефакторинг.

let read_network_config () =
    let init_data = read_line () in
    Scanf.sscanf init_data "%d %d %d" (fun n l e -> (n, l, e))


let create_disconnected_network nodes_number =
    Array.make_matrix nodes_number nodes_number 0


let connect_nodes network edges_number =
    for i = 0 to edges_number - 1 do
        let edge = read_line () in
        let n1, n2 = Scanf.sscanf edge "%d %d" (fun n1 n2 -> (n1, n2)) in
        network.(n1).(n2) <- 1;
        network.(n2).(n1) <- 1;
    done


let read_gateways gateway_number =
     Array.init gateway_number (fun i -> read_int ())


let search_nodes_to_disconnect network gateways skynet_agent_position =
    let to_destroy = Array.map (fun i -> if network.(i).(skynet_agent_position) = 1 then (Some i, Some skynet_agent_position) else (None, None)) gateways in
    let e = Array.fold_left (fun a b ->
        match a, b with
        | (None, None), (None, None) -> (None, None)
        | (Some x, Some y), (None, None) | (None, None), (Some x, Some y) -> (Some x, Some y)
    ) (None, None) to_destroy in

    let rec find_edge e =
        if e < Array.length network then
            if network.(skynet_agent_position).(e) = 1 then
                (
                    network.(skynet_agent_position).(e) <- 0;
                    network.(e).(skynet_agent_position) <- 0;
                    e
            )
            else find_edge (e + 1)
        else
            0
    in

    match e with
    | (None, None) -> (skynet_agent_position, find_edge 0)
    | (Some x, Some y) -> (
        network.(x).(y) <- 0;
        network.(y).(x) <- 0;
        (x, y)
    )


let disconnect_nodes (a, b) =
    Printf.printf "%d %d\n" a b


let () =
    let nodes_number, edges_number, gateway_number = read_network_config () in

    let network = create_disconnected_network nodes_number in
    connect_nodes network edges_number;

    let gateways = read_gateways gateway_number in

    while true do
        read_int () |> search_nodes_to_disconnect network gateways |> disconnect_nodes
    done

Рефакторинг

При рефакторинге для меня важно было добиться логичной структуры программы, читабельности и спрятать реализацию графа либо в модуль, либо просто в список функций. Делать класс не видел необходимости, потому что у меня не было потребности в динамическом связывании.

После рефакторинга

module Net = struct
    let connect network a b =
        network.(a).(b) <- 1;
        network.(b).(a) <- 1;
        ()

    let disconnect network a b =
        network.(a).(b) <- 0;
        network.(b).(a) <- 0;
        ()

    let has_direct_connection network a b =
        network.(a).(b) = 1

    let find_any_connected_node network node_number =
        let rec find num =
            if num < Array.length network then
                if network.(node_number).(num) = 1 then
                    num
                else
                    find (num + 1)
            else
                node_number
        in

        find 0

    let build nodes_number edges =
        let network = Array.make_matrix nodes_number nodes_number 0 in
        List.iter (fun (a, b) -> connect network a b) edges;
        network
end


let read_network_config () =
    let open Scanf in

    let nodes_number, edges_number, gateway_number =
        let init_data = read_line () in
        sscanf init_data "%d %d %d" (fun n l e -> (n, l, e))
    in

    let rec read_edges = function
        | 0 -> []
        | num -> sscanf (read_line ()) "%d %d" (fun a b -> (a, b)) :: read_edges (num - 1)
    in

    let edges = read_edges edges_number in

    let gateways =
        Array.init gateway_number (fun i -> read_int ()) |> Array.to_list
    in

    nodes_number, edges, gateways


let fight_with_skynet network gateways =
    let destroy_edge a b =
        Net.disconnect network a b;
        Printf.printf "%d %d\n" a b
    in

    let rec stop_skynet_agent () =
        let skynet_agent_position = read_int () in
        let agent_to_gateway_edges =
            List.filter (fun gateway ->
                Net.has_direct_connection network skynet_agent_position gateway)
            gateways
        in
        let connected_node = match agent_to_gateway_edges with
        | [] -> Net.find_any_connected_node network skynet_agent_position
        | connected_gateway :: tl -> connected_gateway
        in
        destroy_edge skynet_agent_position connected_node;

        stop_skynet_agent ()
    in

    stop_skynet_agent ()


let () =
    let nodes_number, edges, gateways = read_network_config () in
    let network = Net.build nodes_number edges in
    fight_with_skynet network gateways

Заключение

В итоге у меня получилось решение, которое и задачу решало, и меня устраивало (во всяком случае, с текущем уровнем знаний в OCaml).

Недостаток решения задач на соревнованиях - нужен только результат, а не поддерживаемый код. Довольно сложно убедить себя в необходимости дорабатывать код, если все тесты пройдены, а возвращаться к коду вряд ли понадобится.