PKU 2942 - Knights of the Round Table

Autor da análise: AtolAtol

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2942

Resumo

Temos que expulsar todos os cavaleiros que não podem participar de nenhuma mesa redonda.
Numa mesa redonda só podem participar um número ímpar de cavaleiros , diferente de 1.
Existem cavaleiros que não se gostam, não podendo sentar um do lado do outro na mesa ( cada cavaleiro tem apenas dois lados… )
É dado um grafo com as arestas indicando quais os cavaleiros que não se gostam.

Solução

Pegue o grafo complementar do grafo dado no enunciado, e assim teremos um grafo G com arestas de vértice (cavaleiro) apenas para os (vértices) cavaleiros que podem do seu lado, ou seja, cavaleiros que se gostam. Como queremos um número impar de cavaleiros na mesa, podem participar apenas aqueles que pertencem a algum ciclo ímpar nesse grafo G. Então a resposta que deve ser devolvida é (N - |pertencem a ciclo ímpar|), ou, (|não pertencem a nenhum ciclo ímpar|).

Para isso, precisamos encontrar os vértices de articulação do grafo, pois em subgrafos que não possuem vértices de articulação todos os vértices se ligam a todos os vértices por pelo menos dois caminhos diferentes. Concluindo que se há algum ciclo ímpar C nesse subgrafo então todo vértice deste subgrafo pertence a algum ciclo ímpar, pois podemos chegar a um vértice V desse ciclo C por pelo menos dois caminhos diferentes. Como V pertence a um ciclo ímpar, dá pra mostrar que podemos chegar em V com um número ímpar de arestas para qualquer vértice do subgrafo. Assim, basta verificar se há algum ciclo ímpar nesse subgrafo induzido onde não há vertice de articulação.

Uma maneira simples de implementar isso, é rodar o algoritmo de achar vértices de articulação e depois, para cada vértice de articulação, digamos V, fazer uma DFS pintando os vértices atingidos com 0 na primeira DFS, 1 na segunda, e etc, até que todos os vizinhos do vértice de articulação V estejam pintados. Guarde isso num map < pair<int,int> , int >: chego no vizinho X do vértice de articulação V com valor VAL. ( Então para dois vizinhos do vértice V com valor VAL iguais, temos que existe caminho entre esses dois vértices que não passa por V, e portanto temos pelo menos dois caminhos disjuntos entre tais vértices )

Agora basta fazer um bicoloring sem "cruzar" um vértice de articulação, ou seja, sempre que vamos expandir a busca e estamos num vértice de articulação, basta olhar se o vértice para onde queremos ir tem o mesmo valor VAL (definido no paragrafo acima) do vértice de onde viemos1. Isso para garantir que realmente haja um ciclo, pois ao "cruzarmos" o vértice de articulação para um outro valor, não teremos mais um ciclo que envolva os vértices iniciais (antes de cruzar) e os finais (depois de cruzar), já que o único caminho entre tais vértices é passando pelo vértice de articulação.

Agora nada melhor do que uma boa força bruta, verificando para cada vértice se ele está ou não num ciclo impar, rodando um bicoloring com essas propriedades extras.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License