Ir al contenido (saltar navegación)

Árboles libres

Tiempo máximo: 1,000-3,000 sMemoria máxima: 4096 KiB

Se dice que un grafo no dirigido es un árbol libre si es acíclico y conexo (o dicho de otra manera, todo par de vértices está conectado por exactamente un camino).

De los dos grafos siguientes, solamente el de la izquierda es árbol libre.

Grafos no dirigidos que son árbol libre o no

El problema consiste en decidir si un grafo no dirigido es árbol libre o no.

Entrada

La entrada está compuesta por diversos casos de prueba. Para cada caso, la primera línea contiene el número de vértices del grafo, V (entre 1 y 10.000), y la segunda el número de aristas, A (entre 0 y 100.000). A continuación aparecen A líneas, cada una con dos enteros que representan los extremos de cada una de las aristas (valores entre 0 y V − 1). Los grafos no contienen aristas de un vértice a sí mismo ni más de una arista que conecte un mismo par de vértices.

Salida

Para cada caso de prueba se escribirá SI si el grafo es árbol libre y NO en caso contrario.

Entrada de ejemplo

6
5
0 5
0 2
2 1
2 3
4 3
6
5
0 1
1 2
2 3
3 0
4 5

Salida de ejemplo

SI
NO