Pagini recente » Cod sursa (job #114196) | Cod sursa (job #1476958) | Cod sursa (job #2714704) | Cod sursa (job #1004437) | Cod sursa (job #2927164)
def citire_lista_adiacenta(fisier: str = "ctc.in"):
with open(fisier) as f:
nr_noduri, nr_muchii = [int(x) for x in f.readline().split()]
lista = [[] for _ in range(nr_noduri + 1)]
for _ in range(nr_muchii):
linie = f.readline().split()
x , y = int(linie[0]), int(linie[1])
lista[x].append(y)
return lista
lista = citire_lista_adiacenta()
vizitat = set([])
lista_componente_conexe = [[] for _ in range(len(lista))]
ordin = []
def dfs(nod):
vizitat.add(nod)
ordin.append(nod)
for vecin in lista[nod]:
if vecin not in vizitat:
dfs(vecin)
def dfs_conex(nod):
vizitat.add(nod)
lista_componente_conexe[nr_componente_conexe].append(nod)
for vecin in lista[nod]:
if vecin not in vizitat:
dfs_conex(vecin)
if __name__ == "__main__":
nr_componente_conexe = 0
for i in range(1, len(lista)):
if i not in vizitat:
dfs(i)
vizitat.clear()
for i in range(len(ordin) - 2, 0, -1):
nod = ordin[i]
if nod not in vizitat:
nr_componente_conexe += 1
dfs_conex(nod)
print(nr_componente_conexe)
for i in range(1, len(lista_componente_conexe)):
print(*lista_componente_conexe[i])