Aventura Bipartida em um Mundo Conectado: Desafio em Grafos

18112023 1316 2023 Q3 MCTA02717 Teoria dos Grafos Aventura Bipartida em um Mundo Conectado Descrigao Painel Meuscursos 2023Q3IG Entrega 2 25outubro TEORICOS e 4novembro PRATICOS Aventura Bipartida em um Mundo Conectado Descrido UVisuvalizar envios Aventura Bipartida em um Mundo Conectado 4 Data de entrega sdbado 4 Nov 2023 2300 0 Nbmero maximo de arquivos Tipo de trabalho Trabalho individual Vocé acaba de ser convocado para uma missGo emocionante em um mundo mdgico chamado Grafoldndia onde os habitantes sdo representados por pontos interconectados criando um intrigante complexo sistema de relacdes No entanto had uma particularidade interessante esses habitantes sdo divididos em dois clds rivais os Azuis os Vermelhos Para manter a paz em Grafoldndia é crucial determinar se as relacdes entre esses habitantes podem ser classificadas em duas facoées distintas de modo que nado haja conflitos internos em cada cla Sua tarefa é criar um algoritmo que avalie se Grafolandia pode ser organizada dessa maneira separando seus habitantes em dois clas sem que haja conflitos internos Vocé precisa desenvolver uma fundo que descubra se é possivel alcancar essa harmonia A paz em Grafolandia depende de vocé e do sucesso dessa missdo Que a sabedoria e a determinacgdo estejam com vocé Instrugoes Independente dos resultados dos testes o nGo cumprimento dos critérios abaixo implicarad em nota zero para esta atividade Qualquer duvida entre em contato e Vocé deve resolver esse problema em linguagem C usando grafos que devem ser representados por listas de adjacéncias e Vocé deve incluir no inicio do seu programa uma breve cabecalho contendo no minimo o seu nome e RA e Se vocé precisar implementar uma busca em largura vocé precisa implementar uma estrutura de dados Fila e Se vocé precisar implementar o algoritmo de Kruskal vocé precisa implementar uma estrutura de dados UnionFind e Se vocé precisar implementar o algoritmo de Prim vocé precisa implementar uma estrutura de dados Heap Indente corretamente o seu Cddigo e inclua comentdrios necessdrios no decorrer do seu programa Entrada A primeira linha da entrada consiste de dois inteiros V e E separados por espaco onde 1V 1000 e0 Es VV 12 representando o nUmero de habitantes e o numero de relagdes de conflito entre os habitantes da Grafoldndia respectivamente Cada habitante é representado por um cdédigo numérico entre Oe V 1 Cada uma das préximas E linhas consiste de um par de inteiros x e y separados por espaco onde 0xy V 1 que representa a existéncia de um conflito entre os habitantes de cddigos xe y httpsmoodleufabcedubrmodvplviewphpid289561 13 18112023 1316 2023 Q3 MCTA02717 Teoria dos Grafos Aventura Bipartida em um Mundo Conectado Descrição httpsmoodleufabcedubrmodvplviewphpid289561 23 VPL Saída Se for possível dividir a Grafolândia em dois clãs em que não haja conflitos internos seu programa deve imprimir três linhas a primeira contendo o texto PAZ e as duas últimas contendo os habitantes de cada clã separados por espaço Os habitantes devem ser impressos em ordem crescente numérica Se não for possível a divisão seu programa deve imprimir duas linhas a primeira contendo o texto GUERRA e a última contendo uma sequência de habitantes que comprovem o impedimento da divisão essa sequência não necessariamente deve ser em ordem crescente numérica ela precisa realmente indicar o impedimento ATENÇÃO A saída do seu programa pode ser diferente da saída mostrada nos exemplos a seguir Isso não necessariamente significa que seu programa está errado ele só encontrou outro motivo para haver guerra O corretor irá detectar isso Exemplos Entrada 1 5 5 0 1 0 4 2 4 3 1 3 4 Saída 1 PAZ 0 2 3 1 4 Entrada 2 5 6 0 1 0 4 0 2 2 4 3 1 3 4 Saída 2 GUERRA 2 0 4 Lista 1 Seguir para Desbravando os Ciclos de Grafolândia 18112023 1316 2023 Q3 MCTA02717 Teoria dos Grafos Aventura Bipartida em um Mundo Conectado Descrigao Este 6 o Ambiente Virtual de Aprendizagem da UFABC para apoio ao ensino presencial e semipresencial Esta plataforma permite que os usuarios educadoresalunos possam criar cursos gerencidlos e participar de maneira colaborativa Informaao Conhecca a UFABC Conheca o NII Conheca o Netel Contato Av dos Estados 5001 Bairro Bangu Santo André SP Brasil CEP 09210580 Siganos Universidade Federal do ABC Moodle 2023 Portugués Brasil pt br English en Portugués Brasil pt br Obter o aplicativo para dispositivos méveis httpsmoodleufabcedubrmodvplviewphpid289561 33