Задача: 310. Minimum Height Trees
Сложность: medium

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

Дано дерево из n узлов, помеченных от 0 до n - 1, и массив из n - 1 ребер, где edges[i] = [ai, bi] указывает на наличие неориентированного ребра между узлами ai и bi в дереве. Вы можете выбрать любой узел дерева в качестве корня. Когда вы выбираете узел x в качестве корня, дерево имеет высоту h. Среди всех возможных корневых деревьев те, которые имеют минимальную высоту (то есть min(h)), называются деревьями с минимальной высотой (MHT).

Верните список всех меток корней MHT. Вы можете вернуть ответ в любом порядке.

Высота корневого дерева — это количество ребер на самом длинном нисходящем пути между корнем и листом.

Пример:

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

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

1⃣Создание списка смежности
Создайте список смежности, представляющий граф.

2⃣Удаление листьев
Начните с удаления всех листьев. Лист — это узел с одной гранью. В каждой итерации удаляйте текущие листья и обновляйте список смежности. Новые листья будут вершинами, которые стали листьями после удаления предыдущих листьев.

3⃣Повторение процесса
Повторяйте процесс до тех пор, пока не останется два или менее узлов. Эти узлы будут корнями деревьев с минимальной высотой (MHT).

😎 Решение:

public class Solution {
    public IList<int> FindMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return new List<int> { 0 };
        
        var adj = new List<HashSet<int>>();
        for (int i = 0; i < n; i++) adj.Add(new HashSet<int>());
        foreach (var edge in edges) {
            adj[edge[0]].Add(edge[1]);
            adj[edge[1]].Add(edge[0]);
        }
        
        var leaves = new List<int>();
        for (int i = 0; i < n; i++) {
            if (adj[i].Count == 1) leaves.Add(i);
        }
        
        int remainingNodes = n;
        while (remainingNodes > 2) {
            remainingNodes -= leaves.Count;
            var newLeaves = new List<int>();
            foreach (var leaf in leaves) {
                var neighbor = adj[leaf].First();
                adj[neighbor].Remove(leaf);
                if (adj[neighbor].Count == 1) newLeaves.Add(neighbor);
            }
            leaves = newLeaves;
        }
        
        return leaves;
    }
}

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

Задача: 1129. Shortest Path with Alternating Colors
Сложность: medium

Вам дано целое число n, количество узлов в ориентированном графе, где узлы помечены от 0 до n - 1. Каждое ребро в этом графе может быть красным или синим, и могут быть самопетли и параллельные ребра.

Вам даны два массива redEdges и blueEdges, где:
redEdges[i] = [ai, bi] указывает, что в графе существует направленное красное ребро от узла ai к узлу bi, и
blueEdges[j] = [uj, vj] указывает, что в графе существует направленное синее ребро от узла uj к узлу vj.
Верните массив answer длины n, где каждый answer[x] — это длина кратчайшего пути от узла 0 до узла x, такого что цвета ребер чередуются вдоль пути, или -1, если такого пути не существует.

Пример:

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]

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

1⃣Создание структуры данных и инициализация:
Создайте список смежности adj, который будет содержать пары (сосед, цвет) для каждого узла.
Создайте массив answer длиной n, инициализированный значением -1, чтобы хранить длину кратчайшего пути для каждого узла.
Создайте 2D массив visit для отслеживания, были ли узлы посещены с использованием ребра определённого цвета.

2⃣Инициализация очереди и начальных условий:
Создайте очередь для хранения трёх значений (узел, количество шагов, цвет предыдущего ребра).
Добавьте в очередь начальный узел (0, 0, -1) и установите visit[0][0] и visit[0][1] в true, так как повторное посещение узла 0 бессмысленно.

3⃣Обработка очереди и обновление результата:
Пока очередь не пуста, извлекайте элемент из очереди и получайте (узел, количество шагов, цвет предыдущего ребра).
Для каждого соседа, если сосед не был посещён с использованием ребра текущего цвета и текущий цвет не равен предыдущему, обновите массив answer и добавьте соседа в очередь.

😎 Решение:

public class Solution {
    public int[] ShortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        var adj = new Dictionary<int, List<(int, int)>>();
        foreach (var edge in redEdges) {
            if (!adj.ContainsKey(edge[0])) adj[edge[0]] = new List<(int, int)>();
            adj[edge[0]].Add((edge[1], 0));
        }
        foreach (var edge in blueEdges) {
            if (!adj.ContainsKey(edge[0])) adj[edge[0]] = new List<(int, int)>();
            adj[edge[0]].Add((edge[1], 1));
        }

        var answer = new int[n];
        Array.Fill(answer, -1);
        var visit = new bool[n, 2];
        var queue = new Queue<(int node, int steps, int prevColor)>();
        queue.Enqueue((0, 0, -1));
        answer[0] = 0;
        visit[0, 0] = true;
        visit[0, 1] = true;

        while (queue.Count > 0) {
            var (node, steps, prevColor) = queue.Dequeue();
            if (!adj.ContainsKey(node)) continue;

            foreach (var (neighbor, color) in adj[node]) {
                if (!visit[neighbor, color] && color != prevColor) {
                    if (answer[neighbor] == -1) answer[neighbor] = steps + 1;
                    visit[neighbor, color] = true;
                    queue.Enqueue((neighbor, steps + 1, color));
                }
            }
        }
        return answer;
    }
}

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