Verificar si el Grafo es Eficiente
Dado un grafo no dirigido con
v vértices y e aristas, se te solicita comprobar si es eficiente. Un grafo se considera eficiente si es posible desplazarse desde cualquier nodo a cualquier otro nodo recorriendo como máximo 2 aristas.Entrada
La primera línea de la entrada contiene dos números enteros
v (1 ≤ v ≤ 100) y e (1 ≤ e ≤ 10 000).Las siguientes
e líneas contienen pares de números enteros v1, v2 (1 ≤ v1, v2 ≤ v) que representan una arista entre v1 y v2.Salida
El programa debe imprimir
Yes si el grafo es eficiente y No en caso contrario.Ejemplos
Entrada | Salida |
4 3
1 2
2 3
3 1 | No |
4 4
1 2
2 3
3 1
1 4 | Yes |
Explicación
- El vértice 4 no está conectado con los demás ⇒ no es posible llegar desde el vértice 4 a cualquier otro recorriendo como máximo 2 aristas.
- Es posible llegar a cualquier vértice desde cualquier otro vértice recorriendo como máximo 2 aristas.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB