Pagini recente » Cod sursa (job #2729942) | Cod sursa (job #929134) | Cod sursa (job #1962477) | Cod sursa (job #297698) | Cod sursa (job #2928006)
from collections import defaultdict, deque
f = open('ctc.in')
n, m = [int(x) for x in f.readline().split()]
adjList = defaultdict(list)
i = 0
while i < m:
n1, n2 = [int(x) for x in f.readline().split()]
adjList[n1].append(n2)
i += 1
f.close()
print(adjList)
index = 0
indexes = [0] * (n + 1)
lowlinks = [0] * (n + 1)
stackStatus = [False] * (n + 1)
stack = deque()
nrComponents = 0
connectedComponents = deque()
def DFS(node):
global index
global nrComponents
indexes[node] = index
lowlinks[node] = index
stack.append(node)
stackStatus[node] = True
index += 1
for vecin in adjList[node]:
if indexes[vecin] == 0:
DFS(vecin)
lowlinks[node] = min(lowlinks[node], lowlinks[vecin])
elif stackStatus[vecin]:
lowlinks[node] = min(lowlinks[node], indexes[vecin])
if lowlinks[node] == indexes[node]:
currentComponent = deque()
nrComponents += 1
el = -1
while node != el:
el = stack.pop()
currentComponent.append(el)
stackStatus[el] = False
connectedComponents.append(currentComponent)
DFS(list(adjList.keys())[0])
out = open('ctc.out', 'a')
out.write(str(nrComponents))
out.write("\n")
while connectedComponents:
component = connectedComponents.pop()
while component:
out.write(str(component.pop()))
out.write(' ')
out.write("\n")
out.close()