Pagini recente » Cod sursa (job #375301) | Cod sursa (job #2989795) | Cod sursa (job #2178077) | Cod sursa (job #429808) | Cod sursa (job #2928241)
f = open("ctc.in", "r")
g = open("ctc.out", "w")
n, m = f.readline().split(' ')
n = int(n)
m = int(m)
la = [[] for i in range(n + 1)]
lat = [[] for i in range(n + 1)]
for linie in f:
x, y = linie.split(' ')
x = int(x)
y = int(y)
la[x].append(y)
lat[y].append(x)
f.close()
def dfsOrd(v, fin, viz): #dfs + nodurile in ordinea finalizarii
viz[v] = 1
for u in la[v]:
if viz[u] == 0:
dfsOrd(u, fin, viz)
fin = fin.append(v) #nodul a fost finalizat
def dfsAfis(v, viz):
viz[v] = 1
g.write(f'{str(v)} ')
for u in lat[v]:
if viz[u] == 0:
dfsAfis(u, viz)
fin = [] #nodurile in ordinea finalizarii din dfs
viz = [0 for i in range(n+1)] #marcam ca nevizitate pt dfs
nr = 1 #nr ctc
for v in range(1, n+1):
if viz[v] == 0:
dfsOrd(v, fin, viz)
nr += 1
viz = [0 for i in range(n+1)] #marcam ca nevizitate pt dfs pt graf transpus
g.write(f'{str(nr)}\n')
while fin:
nod = fin.pop()
if viz[nod] == 0:
dfsAfis(nod, viz)
g.write('\n')