Estoy haciendo un problema en Spoj que básicamente se reduce a detectar si un gráfico es bipartito. Estoy tratando de colorear el gráfico usando dfs, pero es demasiado lento. Algún tipo comenta esto

No bfs, no dfs, no bipartie graph. Simple Union-Find Set lo haría (con velocidad, de hecho). Sugerencia n. ° 1: El ciclo de longitud par no afecta la divisibilidad por 2 (wow, tantos i en una palabra) de la longitud de las rutas entre dos nodos. Sugerencia n. ° 2: (SPOILER) deje que dist [i] sea la distancia de una ruta de i a padre [i]. actualícelo con la función de búsqueda y unión. Se puede mejorar para que dist sea una matriz bool.

¿Alguien podría explicar lo que quiere decir con esto? Creo que lo que está tratando de decir es que para cada nodo, usted almacena la distancia entre el nodo y el elemento representativo. Luego, si intenta fusionar dos nodos en el mismo conjunto, y si tienen la misma paridad, entonces crea un ciclo impar, por lo que el gráfico no puede ser bipartito. Sin embargo, no entiendo cómo se implementaría esto. ¿Cómo puedes fusionar dos conjuntos mientras cuentas la distancia? ¿No tendría que mirar a través de todo el conjunto para encontrar todos los elementos para actualizar?

Enlace al problema:https: //www.spoj.com/problems/BUGLIFE