Pagini recente » Cod sursa (job #48925) | Cod sursa (job #1819946) | Cod sursa (job #2230899) | Cod sursa (job #1346752) | Cod sursa (job #2928645)
from collections import defaultdict
import sys
sys.setrecursionlimit(30000)
def DFSfirst(node):
viz[node]=1
for neigh in graph[node]:
if viz[neigh]==0:
DFSfirst(neigh)
stack.append(node)
def reverseGraph(graph):
revGraph = defaultdict(list)
for i in graph.keys():
for j in graph[i]:
revGraph[j].append(i)
return revGraph
def DFSsecond(node):
viz2[node]=1
rezlist[rez].append(node)
for neigh in revGraph[node]:
if viz2[neigh]==0:
DFSsecond(neigh)
stack = []
graph = defaultdict(list)
with open("ctc.in") as file:
n, m = [int(x) for x in file.readline().split(" ")]
for _ in range(m):
a, b = [int(x) for x in file.readline().split(" ")]
graph[a].append(b)
viz = [0 for x in range(n+1)]
viz2 = [0 for x in range(n+1)]
for node in range(1,n+1):
if viz[node]==0:
DFSfirst(node)
revGraph = reverseGraph(graph)
rez=0
rezlist = defaultdict(list)
while stack!=[]:
x = stack.pop()
if viz2[x]==0:
DFSsecond(x)
rez+=1
for i in rezlist.keys():
rezlist[i].sort()
with open('ctc.out', 'w') as file:
file.write(str(rez,))
file.write('\n')
for i in rezlist:
file.write(' '.join(map(str,rezlist[i])))
file.write('\n')