from collections import defaultdict
class Grafo:
def __init__(self, vertices):
self.vertices = vertices
self.grafo = defaultdict(list)
def agregar_arista(self, u, v):
self.grafo[u].append(v)
def dfs(self, v, visitados):
visitados[v] = True
for i in self.grafo[v]:
if not visitados[i]:
self.dfs(i, visitados)
def es_semiconexo(self):
# Inicializar todos los vértices como no visitados
visitados = [False] * (self.vertices)
# Realizar una búsqueda en profundidad desde el primer vértice
self.dfs(0, visitados)
# Verificar si todos los vértices fueron visitados
for i in range(self.vertices):
if not visitados[i]:
return False
return True
# Ejemplo de uso
grafo = Grafo(4)
grafo.agregar_arista(0, 1)
grafo.agregar_arista(1, 2)
grafo.agregar_arista(2, 3)
if grafo.es_semiconexo():
print("El grafo es semiconexo")
else:
print("El grafo no es semiconexo")