Cod sursa(job #2936940)

Utilizator ccazacu1Cazacu Cristian - Gabriel ccazacu1 Data 9 noiembrie 2022 18:05:09
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 2.01 kb
#--------------------------------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()