Задача: 261. Graph Valid Tree
Сложность: medium

У вас есть граф из n узлов, помеченных от 0 до n - 1. Вам даны целое число n и список рёбер, где edges[i] = [ai, bi] указывает на то, что существует неориентированное ребро между узлами ai и bi в графе.
Верните true, если рёбра данного графа образуют допустимое дерево, и false в противном случае.

Пример:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

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

1⃣Проверьте, что количество рёбер равно n - 1. Если нет, верните false.

2⃣Используйте итеративный обход в глубину (DFS) для проверки связности графа и отсутствия циклов. Создайте стек для хранения узлов для посещения и множество для отслеживания посещённых узлов. Начните с узла 0.

3⃣Если все узлы посещены и циклы не обнаружены, верните true. В противном случае, верните false.

😎 Решение:

class Solution {
    function validTree($n, $edges) {
        if (count($edges) != $n - 1) {
            return false;
        }
        
        $adjList = array_fill(0, $n, []);
        foreach ($edges as $edge) {
            $adjList[$edge[0]][] = $edge[1];
            $adjList[$edge[1]][] = $edge[0];
        }
        
        $parent = [0 => -1];
        $queue = [0];
        
        while (!empty($queue)) {
            $node = array_shift($queue);
            foreach ($adjList[$node] as $neighbor) {
                if ($neighbor == $parent[$node]) {
                    continue;
                }
                if (isset($parent[$neighbor])) {
                    return false;
                }
                $parent[$neighbor] = $node;
                $queue[] = $neighbor;
            }
        }
        
        return count($parent) == $n;
    }
}

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