---
# System prepended metadata

title: Prévia TP4
tags: [grafos, dfs, dijkstra, prova, mst, bipartido, bfs]

---

---
title: "Prévia do TP4"
tags: [grafos, prova, bfs, dfs, dijkstra, mst, bipartido]
author: "Leonardo Gloria"
layout: default
---

# 🧮 Prévia do TP4
**Tópicos:** BFS, DFS, Grafos Bipartidos, Dijkstra, Árvores Geradoras Mínimas (MST)  
**Quantidade de questões:** 16

**Instruções:** Responda todas as questões. Mostre os passos, algoritmos e estruturas utilizadas (lista de adjacência, matrizes de adjacência, tabelas de distâncias, etc.). Para questões de implementação, entregue o código comentado.

---

### 1.
Dado um grafo não direcionado representando amigos em uma rede social, use **BFS** para descobrir o número mínimo de conexões necessárias para que uma pessoa alcance outra (grau de separação).



---

### 2.
Usando **DFS**, determine se o grafo abaixo é **conexo**.  
Mostre a ordem de visita dos vértices.



---

### 3.
Dado um grafo direcionado representando dependências entre tarefas, use **DFS** para determinar se há um **ciclo**.  
Se houver, exiba um exemplo de ciclo encontrado.



---

### 4.
Construa o grafo de rotas entre cidades e, usando **BFS**, descubra **quantas cidades estão a uma distância de até 2 estradas** da capital.


---

### 5.
Um grupo de estudantes formou pares de “inimizades”. Modele a relação como um grafo e use **bicoloração (2-coloring)** para verificar se é possível dividir os alunos em **dois grupos que não se odeiam**.  
Se não for possível, mostre um **exemplo de conflito**.



---

### 6.
Dado um grafo representando funcionários e projetos (onde uma aresta indica que o funcionário trabalha em determinado projeto), determine se o grafo é **bipartido** e mostre os **conjuntos U e V**.


---

### 7.
Em um mapa de cidades conectadas por rodovias com pesos representando distâncias, aplique o **Algoritmo de Dijkstra** para encontrar o **menor caminho de uma cidade origem até todas as outras**.  
Mostre a tabela de distâncias e o grafo resultante com o caminho mínimo.


---

### 8.
Mostre por que o **Algoritmo de Dijkstra** falha em um grafo que possui **arestas com peso negativo**.  
Forneça um exemplo numérico simples e demonstre o erro passo a passo.


---

### 9.
Um aplicativo de entregas precisa calcular o **menor tempo de entrega** entre armazéns e clientes, considerando o **tempo de tráfego como peso das arestas**.  
Implemente Dijkstra e exiba o tempo mínimo entre o armazém principal e cada cliente.


---

### 10.
Dado o grafo de cidades e custos de ligação, aplique o **Algoritmo de Kruskal** para encontrar a **árvore geradora mínima (MST)**.  
Mostre as arestas escolhidas e o custo total.


---

### 11.
Resolva o mesmo problema do exercício anterior usando o **Algoritmo de Prim**, iniciando de um nó diferente.  
Compare as árvores obtidas e diga se são **únicas** ou **diferentes**.



---

### 12.
Explique como o uso de **disjoint set (Union-Find)** ajuda a detectar **ciclos** durante a construção de uma árvore geradora mínima.


---

### 13.
Um engenheiro deseja conectar computadores com cabos de menor custo possível.  
Monte a árvore geradora mínima e indique qual seria o **ganho percentual** em relação à soma de todos os cabos possíveis.



---

### 14. <!-- Maratona -->
Você recebeu um mapa com **N ilhas e M pontes**. Cada ponte tem um **custo de construção**.  
O governo quer ligar todas as ilhas gastando o mínimo possível.  
Se não for possível conectar todas, imprima **“Impossível”**.  
*(Dica: use Kruskal.)*


---

### 15. <!-- Maratona -->
Dada uma matriz **N×N** representando um mapa onde cada célula tem um custo de travessia, calcule o **custo mínimo** para ir do canto superior esquerdo ao inferior direito, movendo-se apenas nas quatro direções (cima, baixo, esquerda, direita).  
*(Desafio: resolver usando Dijkstra em matriz – grafo implícito.)*

### 16.
MESA - Mesa da Sra Montagny!

Já comentamos as festas da Sra. Montagny à beira do Lake Louise em Banff. Nas suas festas ela se compromete a resolver um outro problema que faz tremer organizadores de jantares em todo o mundo: onde sentar os convidados. A magnata simplifica bastante o problema pedindo aos convidados, no mesmo questionário já comentado, que anote na lista dos convidados aqueles que desejariam ter à sua frente na mesa do jantar. A idéia é ter seus amigos sempre à sua frente, para que a conversa possa fluir melhor. A habilidade da socialite é tamanha que ela foi contratada pelo Fairmont Banff Springs hotel (hotel em que vão ocorrer as finais mundiais do ICPC em 2008: Hotel) para trabalhar no arranjo de mesas de banquete.

Sua tarefa neste problema é auxiliar novamente a magnata. Dados os desejos dos convidados, seu programa deve decidir se é possível dispô-los numa mesa de forma que cada convidado tenha todos os seus amigos no lado oposto da mesa.

## Entrada
A entrada é composta de diversas instâncias. A primeira linha de cada instância contém dois inteiros n (1 <= n <= 100) e m (0 <= m <= n(n-1)/2), onde n é o número de convidados e m é o número de relações de amizade. Cada uma das m linhas seguintes contém dois inteiros u e v indicando que u é amigo de v e v é amigo de u, onde 1 <= u,v <= n.

A entrada termina com final de arquivo.

## Saída
Para cada instância, você deverá imprimir um identificador Instancia k, onde k é o número da instância atual. Na linha seguinte imprima sim se é possível e nao caso contrário.

Após cada instância imprima uma linha em branco.

### Exemplo:
```
Entrada:
3 3
1 2
2 3
1 3
4 3
1 2
1 3
1 4

Saída:
Instancia 1
nao

Instancia 2
sim
```
---

**Observações do professor:**  
- Use notação clara (V, E) e indique a representação escolhida (lista de adjacência, matriz de adjacência, etc.).  
- Para a correção, considerar passos intermediários e justificativa além da resposta final.

