Задача: 684. Redundant Connection
Сложность: medium

В этой задаче дерево — это неориентированный граф, который является связным и не содержит циклов.

Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе.

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

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

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

1⃣Для каждого ребра (u, v) создайте представление графа с использованием списка смежности. Это позволит легко выполнять обход в глубину (DFS) для проверки соединений между узлами.

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

3⃣Верните дублирующееся ребро, которое встречается последним в исходных данных. Это обеспечит корректность решения, даже если существует несколько ответов.

😎 Решение:

class Solution:
    def __init__(self):
        self.seen = set()
        self.MAX_EDGE_VAL = 1000

    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(self.MAX_EDGE_VAL + 1)]

        for edge in edges:
            self.seen.clear()
            if graph[edge[0]] and graph[edge[1]] and self.dfs(graph, edge[0], edge[1]):
                return edge
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])
        return []

    def dfs(self, graph: List[List[int]], source: int, target: int) -> bool:
        if source not in self.seen:
            self.seen.add(source)
            if source == target:
                return True
            for nei in graph[source]:
                if self.dfs(graph, nei, target):
                    return True
        return False

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

Задача: 1273. Delete Tree Nodes
Сложность: medium

Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве.

Пример:

Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2

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

1⃣Постройте дерево из заданных узлов, значений и родителей.

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

3⃣Удалите отмеченные узлы и их поддеревья и верните количество оставшихся узлов.

😎 Решение:

def deleteTreeNodes(nodes, parent, value):
    from collections import defaultdict, deque
    
    tree = defaultdict(list)
    for i in range(nodes):
        if parent[i] != -1:
            tree[parent[i]].append(i)
    
    def dfs(node):
        total_sum = value[node]
        total_count = 1
        for child in tree[node]:
            child_sum, child_count = dfs(child)
            total_sum += child_sum
            total_count += child_count
        if total_sum == 0:
            return 0, 0
        return total_sum, total_count
    
    return dfs(0)[1]

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