Teoria dos Grafos - Desvendando a Magia das Conexões na Grafolândia

18112023 1313 2023 Q3 MCTA02717 Teoria dos Grafos Desvendando a Magia das Conexões na Grafolândia Descrição httpsmoodleufabcedubrmodvplviewphpid292230forceview1 14 Painel Meus cursos 2023Q3TG Entrega 3 22novembro Desvendando a Magia das Conexões na Grafolândia 2023 Q3 MCTA02717 Teoria dos Grafos Descrição Enviar Editar Visualizar envios Desvendando a Magia das Conexões na Grafolândia Data de entrega quinta 23 Nov 2023 0100 Número máximo de arquivos 1 Tipo de trabalho Trabalho individual À medida que Grafolândia emergiu dos sombrios tempos de guerra e as conexões mínimas entre os povoados voltaram a ser restabelecidas as estradas voltaram a ter suas propriedades mágicas os caminhos só permitem avançar mas nunca retroceder Agora mais do que nunca os habitantes anseiam por construir vários caminhos de deslocamento entre os povoados e certamente caminhos que os permitam voltar ao seu povoado de origem Como várias estradas já estão construídas é preciso primeiro detectar quais povoados já estão em regiões altamente conectadas isto é regiões em que quaisquer dois povoados têm uma estrada que os conectam em ambas as direções Sua missão agora é detectar onde no mapa atual essas regiões já existem Instruções Independente dos resultados dos testes o não cumprimento dos critérios abaixo implicará em nota zero para esta atividade Qualquer dúvida entre em contato Você deve resolver esse problema em linguagem C usando grafosdigrafos que devem ser representados por listas de adjacências Você deve incluir no início do seu programa uma breve cabeçalho contendo no mínimo o seu nome e RA Se você precisar implementar uma busca em largura você precisa implementar uma estrutura de dados Fila Se você precisar implementar o algoritmo de Kruskal você precisa implementar uma estrutura de dados UnionFind Use o algoritmo de ordenação disponível no material de aula Se você precisar implementar o algoritmo de Prim você precisa implementar uma estrutura de dados Heap Se você precisar implementar o algoritmo de Tarjan você precisa implementar uma estrutura de dados Pilha Indente corretamente o seu código e inclua comentários necessários no decorrer do seu programa Entrada A primeira linha da entrada consiste de dois inteiros V e E separados por espaço onde 1 V 1000 e 0 E VV 1 representando o número de povoados e o número de estradas que já foram construídas na Grafolândia respectivamente Cada povoado é representado por um código numérico entre 0 e V 1 Cada uma das próximas E linhas consiste de um par de números inteiros separados por espaços x y onde 0 x y V 1 que indicam que há uma estrada mágica do povoado x para o povoado y Saída A primeira linha da saída deve ser a frase Ha X regioes altamente conectadas onde X deve ser corretamente substituído pela quantidade de regiões altamente conectadas encontradas Se X 1 então escreva a frase Ha 1 regiao altamente conectada Não use acentos Cada uma das X linhas seguintes deve contar todos os povoados de uma região altamente conectada da Grafolândia em ordem crescente do código numérico e separados por espaço conforme os exemplos abaixo As regiões em si não têm uma ordem específica Exemplos 18112023 1313 2023 Q3 MCTA02717 Teoria dos Grafos Desvendando a Magia das Conexões na Grafolândia Descrição httpsmoodleufabcedubrmodvplviewphpid292230forceview1 24 Teste 1 Entrada 7 15 0 2 0 6 2 3 3 5 4 0 4 1 4 3 4 5 4 6 5 1 5 4 6 0 6 1 6 3 6 4 Possível saída Ha 2 regioes altamente conectadas 1 0 2 3 4 5 6 Teste 2 Entrada 14 32 1 3 1 5 2 4 2 5 3 1 3 2 3 4 4 0 4 5 5 0 5 1 5 2 5 7 6 7 7 8 7 13 9 8 9 12 9 13 10 8 10 11 10 12 11 12 11 13 12 8 12 10 12 11 13 6 13 7 13 9 13 10 13 11 Possível saída Ha 4 regioes altamente conectadas 0 8 6 7 9 10 11 12 13 1 2 3 4 5 18112023 1313 2023 Q3 MCTA02717 Teoria dos Grafos Desvendando a Magia das Conexões na Grafolândia Descrição httpsmoodleufabcedubrmodvplviewphpid292230forceview1 34 VPL Teste 3 Entrada 5 16 0 1 0 2 0 3 0 4 1 0 1 2 1 4 2 0 2 1 2 4 3 1 3 2 4 0 4 1 4 2 4 3 Única saída possível Ha 1 regiao altamente conectada 0 1 2 3 4 Conectando Povoados Distantes na Grafolândia Seguir para Lista 4 Este é o Ambiente Virtual de Aprendizagem da UFABC para apoio ao ensino presencial e semipresencial Esta plataforma permite que os usuários educadoresalunos possam criar cursos gerenciálos e participar de maneira colaborativa Informação Conheça a UFABC Conheça o NTI Conheça o Netel Contato Av dos Estados 5001 Bairro Bangu Santo André SP Brasil CEP 09210580 Siganos 18112023 1313 2023 Q3 MCTA02717 Teoria dos Grafos Desvendando a Magia das Conexões na Grafolândia Descrição httpsmoodleufabcedubrmodvplviewphpid292230forceview1 44 Universidade Federal do ABC Moodle 2023 Português Brasil ptbr English en Português Brasil ptbr Obter o aplicativo para dispositivos móveis 18112023 1313 2023 Q3 MCTA02717 Teoria dos Grafos Conectando Povoados Distantes na Grafolândia Descrição httpsmoodleufabcedubrmodvplviewphpid292229 13 Painel Meus cursos 2023Q3TG Entrega 3 22novembro Conectando Povoados Distantes na Grafolândia 2023 Q3 MCTA02717 Teoria dos Grafos Descrição Enviar Editar Visualizar envios Conectando Povoados Distantes na Grafolândia Data de entrega quinta 23 Nov 2023 0100 Número máximo de arquivos 1 Tipo de trabalho Trabalho individual Agora que a Grafolândia emergiu dos sombrios tempos de guerra o momento é de reconstrução e renovação Os cidadãos deste mágico reino enfrentam uma necessidade urgente restabelecer a intrincada teia de conexões que une os povoados assegurando que todos estejam interligados No entanto os efeitos devastadores da guerra deixaram os cofres públicos vazios impondo uma restrição crucial é vital estabelecer uma única ligação entre quaisquer dois povoados de forma que no final de todas as obras os gastos sejam o menor possível Instruções Independente dos resultados dos testes o não cumprimento dos critérios abaixo implicará em nota zero para esta atividade Qualquer dúvida entre em contato Você deve resolver esse problema em linguagem C usando grafos que devem ser representados por listas de adjacências Você deve incluir no início do seu programa uma breve cabeçalho contendo no mínimo o seu nome e RA Se você precisar implementar uma busca em largura você precisa implementar uma estrutura de dados Fila Se você precisar implementar o algoritmo de Kruskal você precisa implementar uma estrutura de dados UnionFind Use o algoritmo de ordenação disponível no material de aula Se você precisar implementar o algoritmo de Prim você precisa implementar uma estrutura de dados Heap Indente corretamente o seu código e inclua comentários necessários no decorrer do seu programa Entrada A primeira linha da entrada consiste de dois inteiros V e E separados por espaço onde 1 V 1000 e 0 E VV 12 representando o número de povoados e o número de estradas que poderiam ser construídas na Grafolândia respectivamente Cada povoado é representado por um código numérico entre 0 e V 1 Cada uma das próximas E linhas consiste de um trio de números separados por espaços sendo dois inteiros x y e um número real w onde 0 x y V 1 e 0 w 500 que indicam que a criação de uma estrada entre o povoado x e o povoado y irá custar w aos cofres públicos Você pode considerar que as E possibilidades de estradas se todas escolhidas certamente conectariam a Grafolândia Saída Seu programa deve indicar na primeira linha o custo mínimo que será cobrado dos cofres públicos para a construção de todas as estradas necessárias para conectar os povoados da Grafolândia com duas casas decimais Nas próximas V 1 linhas deve imprimir um par x y de inteiros por linha que indicam que a estrada entre os povoados x e y deve ser construída Não há uma ordem específica para essa resposta Exemplos Teste 1 18112023 1313 2023 Q3 MCTA02717 Teoria dos Grafos Conectando Povoados Distantes na Grafolândia Descrição httpsmoodleufabcedubrmodvplviewphpid292229 23 Entrada 6 5 0 3 367115886309872 0 4 324998711513348 1 2 416953607385499 1 5 211701105886336 4 5 258518695039362 Possível saída 157929 1 5 4 5 0 4 0 3 1 2 Teste 2 Entrada 8 13 0 1 323812089641324 0 6 302457182790761 1 3 453792135601436 1 5 137644866249893 2 3 413104710812971 2 5 193627634556928 2 6 180828721298065 2 7 434499326599484 3 4 837306480627169 3 5 369399542441440 4 5 189346673631658 4 7 470732825259378 5 6 178072698224791 Possível saída 135854 2 3 3 4 1 5 5 6 2 6 0 6 2 7 Teste 3 Entrada 8 8 0 3 895038066654014 0 4 151442836176780 1 4 257700046974838 1 7 392469230360402 2 6 206389384655778 3 5 430995265493799 3 7 311969790382856 6 7 865411574713376 Possível saída 145399 0 3 6 7 0 4 2 6 1 4 3 7 3 5 18112023 1313 2023 Q3 MCTA02717 Teoria dos Grafos Conectando Povoados Distantes na Grafolândia Descrição httpsmoodleufabcedubrmodvplviewphpid292229 33 Universidade Federal do ABC Moodle 2023 Português Brasil ptbr English en Português Brasil ptbr Obter o aplicativo para dispositivos móveis VPL Lista 3 Seguir para Desvendando a Magia das Conexões na Grafolândia Este é o Ambiente Virtual de Aprendizagem da UFABC para apoio ao ensino presencial e semipresencial Esta plataforma permite que os usuários educadoresalunos possam criar cursos gerenciálos e participar de maneira colaborativa Informação Conheça a UFABC Conheça o NTI Conheça o Netel Contato Av dos Estados 5001 Bairro Bangu Santo André SP Brasil CEP 09210580 Siganos