Aventura Bipartida em um Mundo Conectado - MCTA02717

21102023 2232 2023 Q3 MCTA02717 Teoria dos Grafos Aventura Bipartida em um Mundo Conectado Descrição httpsmoodleufabcedubrmodvplviewphpid289561 13 Painel Meus cursos 2023Q3TG Entrega 2 23outubro OU 25outubro Aventura Bipartida em um Mundo Conectado 2023 Q3 MCTA02717 Teoria dos Grafos Descrição Enviar Editar Visualizar envios Aventura Bipartida em um Mundo Conectado Data de entrega quinta 26 Out 2023 0200 Número máximo de arquivos 1 Tipo de trabalho Trabalho individual Você acaba de ser convocado para uma missão emocionante em um mundo mágico chamado Grafolândia onde os habitantes são representados por pontos interconectados criando um intrigante e complexo sistema de relações No entanto há uma particularidade interessante esses habitantes são divididos em dois clãs rivais os Azuis e os Vermelhos Para manter a paz em Grafolândia é crucial determinar se as relações entre esses habitantes podem ser classificadas em duas facções distintas de modo que não haja conflitos internos em cada clã Sua tarefa é criar um algoritmo que avalie se Grafolândia pode ser organizada dessa maneira separando seus habitantes em dois clãs sem que haja conflitos internos Você precisa desenvolver uma função que descubra se é possível alcançar essa harmonia A paz em Grafolândia depende de você e do sucesso dessa missão Que a sabedoria e a determinação estejam com você 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 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 habitantes e o número de relações de conflito entre os habitantes da Grafolândia respectivamente Cada habitante é representado por um código numérico entre 0 e V 1 Cada uma das próximas E linhas consiste de um par de inteiros x e y separados por espaço onde 0 xy V 1 que representa a existência de um conflito entre os habitantes de códigos x e y 21102023 2232 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