Estruturas de Dados 2
| Matrícula | Aluno |
|---|---|
| 180028847 | Vinicius Gabriel R S Brito |
| 180029240 | Wesley Pedrosa dos Santos |
Quarto trabalho da disciplina de Estruturas de Dados 2, com o propósito de avaliar e aplicar os conhecimentos em grafos. Consiste na solução de problemas do LeetCode que exploram abordagens para solução de problemas, evidenciando a assimilação prática dos conceitos teóricos vistos na matéria.
Foram solucionadas quatro questões do LeetCode focadas em problemas que envolvem grafos:
- 210. Course Schedule II
- 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance
- 1584. Min Cost to Connect All Points
- 3604. Minimum Time to Reach Destination in Directed Graph
Neste vídeo, apresentamos um resumo completo do trabalho desenvolvido, abordando os principais pontos discutidos ao longo do projeto.
from collections import defaultdict, deque
from typing import List
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
# Inicializa um dicionário de lista para armazenar o grafo dos cursos e suas dependências
grafo = defaultdict(list)
# Inicializa a lista para contar os pré-requisitos de cada curso (grau de entrada)
grauEntrada = [0] * numCourses
# Cria o grafo e preenche os pré-requisitos
for curso, preRequisito in prerequisites:
grafo[preRequisito].append(curso) # Adiciona uma aresta de 'preRequisito' para 'curso'
grauEntrada[curso] += 1 # Incrementa o grau de entrada do curso
# Inicializa a fila para processar cursos que podem ser realizados (grau de entrada zero)
fila = deque()
# Adiciona os cursos que não têm pré-requisitos
for i in range(numCourses):
if grauEntrada[i] == 0:
fila.append(i)
# Lista para armazenar a ordem de conclusão dos cursos
orderCursos = []
# Realiza a ordem dos cursos na fila
while fila:
cursoAtual = fila.popleft() # Remove o primeiro curso da fila
orderCursos.append(cursoAtual) # Adiciona o curso de conclusão
# Processa os cursos dependentes do curso atual
for cursoDependente in grafo[cursoAtual]:
grauEntrada[cursoDependente] -= 1 # Reduz o grau de entrada desse curso
if grauEntrada[cursoDependente] == 0: # Se não houver pré-requisitos restantes
fila.append(cursoDependente) # Adiciona o curso na fila
# Verifica se todos os cursos foram incluídos na ordem de conclusão
if len(orderCursos) == numCourses:
return orderCursos # Retorna a ordem de cursos possíveis completar todos
else:
return [] # Retorna lista vazia se houver ciclo (impossível completar todos)from typing import List
class Solution:
def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
# monta lista de adjacência: grafo não direcionado e pesado
graph = [[] for _ in range(n)]
for u, v, w in edges:
graph[u].append((v, w))
graph[v].append((u, w))
INF = 10**18
# conta quantas cidades são alcançáveis a partir de 'src'
# com distância total <= distanceThreshold,
# usando DFS com poda por distância
def reachable_from(src: int) -> int:
dist = [INF] * n
dist[src] = 0
def dfs(u: int) -> None:
for v, w in graph[u]:
nd = dist[u] + w
# poda se estourar o limite
if nd > distanceThreshold:
continue
# só segue se realmente melhorar a melhor distância conhecida para v
if nd >= dist[v]:
continue
dist[v] = nd
dfs(v)
dfs(src)
# conta apenas outras cidades, não a própria src
count = 0
for v in range(n):
if v != src and dist[v] <= distanceThreshold:
count += 1
return count
best_city = 0
best_count = float('inf')
# percorre todas as cidades; em caso de empate, fica com a de maior índice
for city in range(n):
cnt = reachable_from(city)
if cnt < best_count or (cnt == best_count and city > best_city):
best_count = cnt
best_city = city
return best_cityfrom typing import List
import heapq
def distancia_manhattan(ponto1: List[int], ponto2: List[int]) -> int:
# Calcula a distância de Manhattan entre dois pontos
return abs(ponto1[0] - ponto2[0]) + abs(ponto1[1] - ponto2[1])
class Solution:
def minCostConnectPoints(self, pontos: List[List[int]]) -> int:
# Calcula o custo mínimo para conectar todos os pontos usando o algoritmo de Prim
# para encontrar a Árvore Geradora Mínima (MST)
n = len(pontos) # Número total de pontos
visitados = [False] * n # Marca os pontos já incluídos na MST
menor_custo = [float('inf')] * n # Armazena o menor custo para conectar cada ponto
menor_custo[0] = 0 # Min-Heap inicializado com o ponto 0 e custo 0
fila_prioridade = [(0, 0)] # Peso total da MST
custo_total = 0 # Inicializa a variável para armazenar o custo total da MST
# Algoritmo de Prim
while fila_prioridade:
custo_atual, ponto_atual = heapq.heappop(fila_prioridade) # Remove o ponto com menor custo da fila
if visitados[ponto_atual]:
continue # Se o ponto já foi visitado ou o custo é maior, ignora
visitados[ponto_atual] = True # Marca o ponto como visitado
custo_total += custo_atual # Adiciona o custo ao peso total da MST
# Considera os pontos adjacentes
for vizinho in range(n):
if not visitados[vizinho]: # Considera pontos ainda não visitados
distancia = distancia_manhattan(pontos[ponto_atual], pontos[vizinho])
if distancia < menor_custo[vizinho]:
menor_custo[vizinho] = distancia
heapq.heappush(fila_prioridade, (distancia, vizinho)) # Atualiza a fila
return custo_totalfrom typing import List
from collections import deque
class Solution:
def minTime(self, n: int, edges: List[List[int]]) -> int:
# Grafo como lista de adjacência: u -> (v, start, end)
adj = [[] for _ in range(n)]
for u, v, start, end in edges:
adj[u].append((v, start, end))
INF = 10**18
dist = [INF] * n
dist[0] = 0
# Fila para BFS com relaxamento
q = deque([0])
in_queue = [False] * n
in_queue[0] = True
while q:
u = q.popleft()
in_queue[u] = False
t = dist[u]
for v, start, end in adj[u]:
# janela fechada
if t > end:
continue
# chegada antes da janela -> espera
if t < start:
nt = start + 1
else:
nt = t + 1 # dentro da janela -> atravessa
# relaxamento
if nt < dist[v]:
dist[v] = nt
if not in_queue[v]:
q.append(v)
in_queue[v] = True
return -1 if dist[n - 1] == INF else dist[n - 1]