Solução Informática - Nivel Intermediário - Semana 3

Solução por Thiago Mota

Conhecimento prévio necessário:

• Flood Fill (BFS)
• Grafos Bipartidos

Vamos interpretar a mesa do problema como um grafo. O problema pede para determinarmos se é possível dividir a mesa em dois lados disjuntos de tal forma que cada vértice de um lado só possua arestas com vértices do outro lado. Grafos com essa propriedade são chamados Grafos Bipartidos. A imagem abaixo mostra um exemplo de grafo bipartido:

Para determinar se um grafo é bipartido, vamos colorir os seus vértices com cores $0$ ou $1$, de forma que cada aresta ligue apenas vértices de cores diferentes. O grafo será bipartido se, e somente se, é possível realizar tal coloração.

Para colorir o grafo, usaremos o seguinte algoritmo, utilizando uma BFS:

1. Inicie uma BFS para cada componente conexa do grafo, em um vértice arbitrário de tal componente, e suponha, sem perda de generalidade, que a cor deste vértice é $0$.
2. Durante a BFS, sendo $u$ o vértice atual no topo da fila, colora cada vizinho $v$ de $u$ com a cor contrária à cor de $u$.
3. Após realizada a BFS em cada componente, o grafo será bipartido se, e somente se, cada aresta do grafo conecta vértices de cores opostas.

Como realizamos apenas uma BFS por componente conexa do grafo, a complexidade final do algoritmo é $O(N+M)$.

Confira o código abaixo para melhor entendimento: