Graph Teory problem | Problema de teoria dos grafos - C language

Encerrado Postado há 2 anos Pago na entrega
Encerrado Pago na entrega

I want a solution of this problem in C language

Data de entrega: sexta, 22 Out 2021, 23:59

Número máximo de arquivos: 1

Tipo de trabalho: Trabalho individual

Museu

O Musée d’Orsay é um importante museu francês. Seus corredores estão repletos de belíssimas e importantíssimas obras de arte. Repleto de bens não fungíveis e valiosíssimos, a segurança do museu precisa ser eficiente e indefectível. E o novo diretor do Musée d’Orsay, Françoise Cachin, sabe disso. Por isso, Françoise pretende implantar um novo esquema de segurança no museu: ele pretende colocar seguranças nas junções dos corredores de tal forma que todo corredor seja vigiado. Todo corredor tem exatamente duas junções e um segurança parado em uma consegue vigiar todos os corredores daquela junção. Além de posicionar os seguranças de forma que todo corredor seja vigiado, o novo diretor quer fazer isso de forma que cada corredor seja vigiado por exatamente um segurança (ele sabe que se dois ou mais seguranças estão guardando um mesmo corredor, esses tendem a abandonar seus postos para conversar).

Como é o caso de todo museu nesse mundão véio, a grana anda curta e Françoise precisa implementar esse novo esquema de vigilância usando o menor número de seguranças possível. Como ele está tendo dificuldades em alocar os seguranças às junções e, para falar a verdade, ele nem sabe se tal tarefa é possível, ele decidiu contratar você, um famoso especialista em algoritmos, para realizar esse job.

Critérios importantes

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 usando grafos que devem ser representados por matrizes de adjacências.

Observações

Você deve incluir, no início do seu programa, uma breve cabeçalho contendo no mínimo o seu nome e RA.

Indente corretamente o seu código e inclua comentários no decorrer do seu programa.

Linguagens aceitas: C

Entrada

A primeira linha da entrada consiste de dois inteiros n m, onde 1 <= n <= 1000 e 0 <= m <= n(n - 1)/2, representando o número de junções e o número de corredores, respectivamente. Cada junção é representada por um código numérico entre 0 e n - 1. Cada uma das próximas m linhas consiste de um par de inteiros u v, separados por espaço, onde 0 <= u, v <= n - 1, que representa a existência de um corredor conectando as junções de códigos u e v.

Saída

A resposta do seu programa deve consistir de um único inteiro z, representando o número mínimo de seguranças necessários no esquema de vigilância idealizado por Françoise, caso isso seja possível, ou da palavra IMPOSSIVEL, caso contrário.

Exemplos

Teste 01

Entrada:

8 3

0 7

1 7

4 7

Saída:

1

Teste 02

Entrada:

6 5

1 3

1 4

2 3

2 5

3 4

Saída:

IMPOSSIVEL

Teste 03

Entrada:

10 11

0 8

0 9

1 6

1 8

1 9

2 7

2 8

3 5

3 6

3 7

3 8

Saída:

4

I attached statements in english

Programação C

ID do Projeto: #31849038

Sobre o projeto

1 proposta Projeto remoto Ativo em há 2 anos

1 freelancer está oferecendo em média $20 para esse trabalho

DaniilLakman

Dear sir! I'd like to express my interesting about your project. I have developed and executed strategies that I believe will bring value to you. I handled tasks very similar to what you outlined in your project. With Mais

$20 USD in 2 dias
(3 Comentários)
2.8