Pagini recente » Cod sursa (job #216823) | Cod sursa (job #3251183) | Cod sursa (job #470258) | Cod sursa (job #396690) | Cod sursa (job #2929859)
# 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()