Estou fazendo um problema no Spoj que basicamente se reduz a detectar se um gráfico é bipartido. Estou tentando apenas colorir o gráfico usando DFS, mas é muito lento. Um cara comenta isso

Sem bfs, sem dfs, sem gráfico bipartido. O Union-Find Set simples o faria (com velocidade, de fato). Dica 1: O ciclo de comprimento uniforme não afeta a divisibilidade por 2 (uau, tantos i em uma palavra) do comprimento dos caminhos entre dois nós. Dica 2: (SPOILER) deixe dist [i] ser a distância de um caminho de i até o pai [i]. atualize-o com a função find and union. Pode ser aprimorado para tornar dist um array boolean

Alguém poderia explicar o que ele quer dizer com isso? Acho que o que ele está tentando dizer é que, para cada nó, você armazena a distância entre o nó e o elemento representativo. Então, se você tentar mesclar dois nós no mesmo conjunto e se eles tiverem a mesma paridade, criará um ciclo ímpar, para que o gráfico não possa ser bipartido. No entanto, não entendo como isso seria implementado. Como você pode mesclar dois conjuntos enquanto calcula a distância? Você não precisaria procurar em todo o conjunto para encontrar todos os elementos a serem atualizados?

Link para o problema:https: //www.spoj.com/problems/BUGLIFE