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:
- 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$$.
- 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$$.
- 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: