Задача: 924. Minimize Malware Spread
Сложность: hard

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока не останется ни одного узла, который можно было бы заразить таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим из initial ровно один узел. Верните тот узел, удаление которого минимизирует M(initial). Если можно удалить несколько узлов, чтобы минимизировать M(initial), верните такой узел с наименьшим индексом. Обратите внимание, что если узел был удален из начального списка зараженных узлов, он все равно может быть заражен позже из-за распространения вредоносного ПО.

Пример:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

👨‍💻 Алгоритм:

1⃣Определить количество зараженных узлов после распространения вредоносного ПО для исходного списка initial.

2⃣Для каждого узла в initial удалить его и вычислить количество зараженных узлов после распространения вредоносного ПО.

3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если есть несколько таких узлов, выбрать узел с наименьшим индексом.

😎 Решение:

function minMalwareSpread($graph, $initial) {
    function dfs($graph, $node, &$infected) {
        for ($neighbor = 0; $neighbor < count($graph); $neighbor++) {
            if ($graph[$node][$neighbor] == 1 && !in_array($neighbor, $infected)) {
                $infected[] = $neighbor;
                dfs($graph, $neighbor, $infected);
            }
        }
    }

    $n = count($graph);
    $initialSet = $initial;
    sort($initial);
    $minInfected = PHP_INT_MAX;
    $bestNode = $initial[0];
    
    foreach ($initial as $node) {
        $infected = $initialSet;
        $infected = array_diff($infected, [$node]);
        foreach ($initialSet as $i) {
            if ($i != $node) {
                dfs($graph, $i, $infected);
            }
        }
        if (count($infected) < $minInfected) {
            $minInfected = count($infected);
            $bestNode = $node;
        }
    }
    
    return $bestNode;
}

Ставь 👍 и забирай 📚 Базу знаний