Pagini recente » Cod sursa (job #2445138) | Cod sursa (job #1374652) | Cod sursa (job #1243674) | Cod sursa (job #1042057) | Cod sursa (job #2936940)
#--------------------------------Problema 4
class Solution: #complexitate O(V + E)
stack = []
marked = []
def CTC(self):
f = open("ctc.in")
v, e = f.readline().split()
v, e = int(v), int(e)
self.marked = [False for i in range(v+1)]
graf = [[] for i in range(v+1)] #construim graful si transpusa pentru Kosaraju
grafT = [[] for i in range(v+1)]
for i in range(e):
vf1, vf2 = f.readline().split()
vf1, vf2 = int(vf1), int(vf2)
graf[vf1].append(vf2)
grafT[vf2].append(vf1)
def DFS(vf, graf):
self.marked[vf] = True #algoritm DFS recursiv
for vecin in graf[vf]:
if not self.marked[vecin]:
DFS(vecin, graf)
self.stack.append(vf)
# DFS(1,graf) #rulam un prim DFS pentru a incarca nodurile pe stack
for i in range(v):
if not self.marked[i]:
DFS(i,graf)
self.marked = [False for i in range(v + 1)]
stack_copy = self.stack
contor = 0 #variabile de output
ctc = []
while stack_copy: #incepem sa scoatem elementele de pe stack-ul umplut anterior
current = stack_copy.pop()
if not self.marked[current]: #daca gasim un varf nevizitat pornim un DFS din varful acela si marcam toate varfurile vizitate
self.stack = []
self.marked[current] = True
DFS(current, grafT)
contor += 1
ctc.append(self.stack) #pentru fiecare DFS pornit avem o componenta tare conexa pe care o salvam
f.close()
g = open("ctc.out", "w")
g.write(f"{contor}\n")
for comp in ctc:
for nr in comp: #scriere in fisier
g.write(f"{nr} ")
g.write("\n")
g.close()
solution = Solution()
solution.CTC()