Número da Lista: 4
Conteúdo da Disciplina: Grafos
| Matrícula | Aluno |
|---|---|
| 21/1061897 | Igor de Sousa Justino |
| 20/2016364 | Guilherme Coelho Mendonça |
O projeto consiste na resolução de questões que examinam o conteúdo visto na sala de aula sobre conceitos iniciais de gráficos
Problema 1: 785 Is Graph Bipartite?
- Nível: Médio
- Implementação:Código 1
A atividade tem como objetivo verificar se um grafo não direcionado pode ser dividido em dois grupos de vértices, de forma que não existam arestas entre vértices do mesmo grupo. O grafo é representado por uma lista de adjacência. A tarefa é retornar true se ele for bipartido e false caso contrário. A solução envolve percorrer o grafo (usando BFS ou DFS) e tentar colorir os vértices com duas cores diferentes. Se houver um conflito de coloração, o grafo não é bipartido. O problema é útil em contextos como formação de grupos e detecção de ciclos ímpares.
Problema 2: 332 Reconstruct Itinerary
- Nível: Difícil
- Implementação:Código 2
O problema consiste em reconstruir um itinerário de viagem a partir de uma lista de passagens aéreas. Cada passagem é representada por um par de cidades (origem, destino), e a tarefa é encontrar uma sequência válida de voos que comece em uma cidade específica (geralmente "JFK") e utilize todas as passagens exatamente uma vez. A solução deve retornar o itinerário em ordem lexicográfica, caso existam múltiplas possibilidades. O problema testa habilidades em grafos, busca em profundidade (DFS) e ordenação, exigindo uma abordagem eficiente para lidar com ciclos e conexões.
- Nível: Difícil
- Implementação:Código 3
O problema consiste em calcular quantos pares de casas em uma rua reta (representada por uma linha numérica) estão a uma certa distância, considerando um ponto fixo que divide a rua. Dadas as posições das casas e do ponto, a tarefa é determinar o número de pares para cada distância possível. A solução exige eficiência na manipulação de arrays e cálculos de distâncias, ajustando para o ponto fixo.
Problema 4: 834 Sum of Distances in Tree
- Nível: Difícil
- Implementação:Código 4
O problema envolve calcular a soma das distâncias de cada nó a todos os outros nós em uma árvore não direcionada. Dada a quantidade de nós e as arestas que os conectam, a tarefa é retornar um array onde cada elemento representa a soma das distâncias de um nó específico a todos os outros.
Linguagem: C
Framework: (Nenhum)
Necessário Python 3 ou superior. Para rodar o código Python:
Salve o código em um arquivo Python, por exemplo, solution.py.
Execute o código no terminal:
$ python solution.py
Se você estiver utilizando Python 3 especificamente, use:
$ python3 solution.py
Este comando irá executar o código e gerar a saída diretamente no terminal.