Verificar se o Grafo é Bipartido
Um grafo é considerado bipartido se for possível colorizá-lo com duas cores de forma que nenhum par de vértices adjacentes partilhe a mesma cor.
Determinar se um grafo é bipartido pode ajudar a revelar estruturas e propriedades específicas, permitindo resolver problemas de forma mais eficiente em áreas como planeamento de tarefas, alocação de recursos e resolução de conflitos. Além disso, os grafos bipartidos possibilitam algoritmos mais simples e otimizações em tarefas como emparelhamento máximo (maximum matching) e coloração de grafos (graph coloring).
É fornecido um grafo não dirigido com
v vértices e e arestas. É necessário verificar se o grafo é bipartido ou não.Entrada
A primeira linha da entrada contém dois inteiros
v (1 ≤ v ≤ 100 000) e e (1 ≤ e ≤ 100 000).As seguintes
e linhas contêm pares de inteiros v1 e v2 (1 ≤ v1, v2 ≤ v), indicando que o vértice v1 está ligado ao vértice v2 e vice-versa.Saída
O programa deve imprimir
Yes se o grafo for bipartido e No caso contrário.Exemplos
Entrada | Saída |
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