Pagini recente » Cod sursa (job #1988868) | Cod sursa (job #1945219) | Cod sursa (job #2839877) | Cod sursa (job #2774013) | Cod sursa (job #2924802)
f = open("date.in", 'r')
fisier = f.readlines()
adiacenta = {}
adiacentaTranspusa = {}
nrNoduri = int(fisier[0].split()[0])
nrMuchii = int(fisier[0].split()[1])
nrComponente = 0
for i in range(1, nrNoduri + 1):
adiacenta[i] = []
adiacentaTranspusa[i] = []
i = 1
while i <= nrMuchii:
adiacenta[int(fisier[i].split()[0])].append(int(fisier[i].split()[1]))
adiacentaTranspusa[int(fisier[i].split()[1])].append(int(fisier[i].split()[0]))
i += 1
stiva = []
def dfs(vizitat, adiacenta, nod):
vizitat[nod] = 0
for vecin in adiacenta[nod]:
if vizitat[vecin] == -1:
dfs(vizitat, adiacenta, vecin)
stiva.append(nod)
def dfst(vizitat, adiacentaTranspusa, nod):
vizitat[nod] = 0
raspuns.append(nod)
for vecin in adiacentaTranspusa[nod]:
if vizitat[vecin] == -1:
dfst(vizitat, adiacentaTranspusa, vecin)
vizitat = [-1] * (nrNoduri + 1)
for i in range(1, nrNoduri + 1):
if vizitat[i] == -1:
dfs(vizitat, adiacenta, i)
listaComponente = []
vizitat = [-1] * (nrNoduri + 1)
for i in range(nrNoduri - 1, 1, -1):
raspuns = []
if vizitat[stiva[i]] == -1:
nrComponente += 1
dfst(vizitat, adiacentaTranspusa, stiva[i])
listaComponente.append(raspuns)
print(nrComponente)
for listaMica in listaComponente:
print(listaMica)