Verificar si el Grafo es Bipartito
Un grafo se considera bipartito si se puede colorear con dos colores de manera que ningún par de vértices adyacentes tenga el mismo color.
Determinar si un grafo es bipartito puede ayudar a identificar estructuras y propiedades importantes, facilitando la resolución de problemas en ámbitos como la programación de horarios, la asignación de recursos y la resolución de conflictos. Además, los grafos bipartitos permiten el uso de algoritmos y optimizaciones más simples en tareas como el emparejamiento máximo y la coloración de grafos.
Se te proporciona un grafo no dirigido con
v vértices y e aristas. Debes verificar si el grafo es bipartito o no.Entrada
La primera línea de la entrada contiene dos enteros
v (1 ≤ v ≤ 100 000) y e (1 ≤ e ≤ 100 000).Las siguientes
e líneas contienen pares de enteros v1, v2 (1 ≤ v1, v2 ≤ v), lo que indica que el vértice v1 está conectado con el vértice v2 y viceversa.Salida
El programa debe imprimir
Yes si el grafo es bipartito y No en caso contrario.Ejemplos
Entrada | Salida |
2 1
2 1 | Yes |
3 2
2 1
1 3 | Yes |
3 3
1 2
1 3
2 3 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB