Cod sursa(job #2929859)

Utilizator ccazacuCazacu Cristian ccazacu Data 26 octombrie 2022 23:50:19
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 3.6 kb
# def Solution():     #complexitate O(V(log V + 1) + E)  deoarece trebuie sa sortam listele de adiacenta O(V log V) si parcurgerea DFS se realizeaza in O(V + E), E este cel putin V -1 graful fiind conectat

#     f = open("input.txt")
#     n, m = f.readline().split()
#     n, m = int(n), int(m)

#     perm = []
#     orders = [0] * (n + 1)

#     nodes = f.readline().split()
#     i = 0
#     for node in nodes:
#         node = int(node)
#         perm.append(node)       #stocam permutarea in variabila perm
#         orders[node] = i        #stocam pozitia din permutare intr-o lista dupa index
#         i += 1
#     adjList = {key: [] for key in range(1, n + 1)}      #cream dictionarul pentru lista de adiacenta

# # # cream lista de adiacenta si sortam nodurile in fiecare lista in functie de ordinea din permutare
#     for i in range(m):
#         node1, node2 = f.readline().split()
#         node1, node2 = int(node1), int(node2)

#         if adjList.get(node1):
#             adjList[node1].append(node2)
#         else:
#             adjList[node1] = [node2]        #daca avem lista vida o reinitializam cu valoarea din nodul 2, alfel dam append
#         if adjList.get(node2):          
#             adjList[node2].append(node1)
#         else:
#             adjList[node2] = [node1]

#     for k in adjList:
#         try:
#             adjList[k] = sorted(adjList[k], key=lambda x: orders[x])
#         except:
#             pass
#     print(adjList)
#     visited = [0] * (n + 1)     #lista pentru a tine cont de varfurile pe care le-am vizitat.
#     dfsPerm = []

#     def DFS(node):      #realizam un DFS recursiv
#             dfsPerm.append(node)
#             visited[node] = 1
#             for nextNode in adjList[node]:
#                 if visited[nextNode] == 0:
#                     DFS(nextNode)

#     DFS(1)      #plecam cu DFS ul din nodul 1 pentru ca el mereu exista din ipoteza
#     if dfsPerm == perm:     #daca DFS ul realizat pe lista de adiacenta sortata pe baza permutarii este egala cu permutarea inseamna ca este posibil sa vizitam nodurile in ordinea data
#         print(1)
#     else:
#         print(0)

# Solution()

import collections

class Solution:

    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)]
        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
            for vecin in graf[vf]:
                if not self.marked[vecin]:
                    DFS(vecin, graf)
            self.stack.append(vf)

        DFS(1,graf)
        self.marked = [False for i in range(v + 1)]
        
        stack_copy = self.stack

        contor = 0
        ctc = []
        while stack_copy:
            current = stack_copy.pop()
            if not self.marked[current]:
                self.stack = []
                self.marked[current] = True
                DFS(current, grafT)
                contor += 1 
                ctc.append(self.stack) 

        f.close()
        g = open("ctc.out", "w")
        g.write(f"{contor}\n") 
        for comp in ctc:
            for nr in comp:
                g.write(f"{nr} ")
            g.write("\n")
        g.close()


solution = Solution()
solution.CTC()