¿El grafo consiste en cliques?
Una clique es un subconjunto de vértices en un grafo no dirigido donde cada par de vértices distintos está conectado por una arista. Dicho de otro modo, una clique es un subgrafo completo en el que todos los vértices son adyacentes entre sí.
Se te proporciona un grafo no dirigido con
v vértices y e aristas. Queremos saber si el grafo dado es una colección de cliques disjuntas.Entrada
La primera línea de la entrada contiene dos números enteros
v (1 ≤ v ≤ 1000) y e (1 ≤ e ≤ ).Las siguientes
e líneas contienen pares de números enteros v1, v2 (1 ≤ v1, v2 ≤ v), indicando que el vértice v1 está conectado con el vértice v2 y viceversa.Salida
El programa debe imprimir
Yes si el grafo dado es un conjunto de cliques disjuntas y No en caso contrario.Ejemplos
Entrada | Salida |
3 3
1 2
2 3
1 3 | Yes |
5 4
1 2
2 3
1 3
4 5 | Yes |
5 5
1 2
2 3
1 3
3 4
4 5 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB