IS GRAPH BIPARTITE MEDIUM
problema
Você recebe um grafo não dirigido de n nós como lista de adjacência: graph[u] lista os
vizinhos de u. O grafo pode estar dividido em várias partes desconectadas.
O grafo é bipartido se dá para separar os nós em dois grupos de modo que toda aresta ligue um nó de um
grupo a um nó do outro. Retorne true se for.
graph = [[1,3],[0,2],[1,3],[0,2]] → true
Um quadrado 0–1–2–3: grupos {0, 2} e {1, 3}.
false
A parte do quadrado se pinta sem problema, mas no triângulo, depois de pintar 5 e 6 com cores diferentes, o 7 é vizinho dos dois e não sobra cor para ele.
Andando por um ciclo, as cores precisam alternar: 0, 1, 0, 1... Para voltar ao início com a cor certa, o ciclo precisa ter um número par de arestas. Um grafo é bipartido se e somente se não tem ciclo ímpar. As duas buscas pintam cada vizinho com a cor oposta e acusam o primeiro ciclo ímpar que encontram.
Restrições: 1 ≤ n ≤ 100 · graph[u] sem repetições e sem u · se v está em graph[u], u está em graph[v]