Pagini recente » Cod sursa (job #2726675) | Cod sursa (job #1539878) | Cod sursa (job #1193524) | Cod sursa (job #1113932) | Cod sursa (job #2536327)
def read_gen(fname):
with open(fname, 'rt') as fin:
for line in fin:
for val in line.split():
yield int(val)
def dfs(g, used, perm, node):
used[node] = True
for x in g[node]:
if used[x] is False:
dfs(g, used, perm, x)
perm.append(node)
def solve(g, gt, n):
used = {x: False for x in range(1, n + 1)}
perm = []
for i in range(1, n + 1):
if used[i] is False:
dfs(g, used, perm, i)
for x in used: used[x] = False
scc = []
perm.reverse()
for x in perm:
if used[x] is False:
new_scc = []
dfs(gt, used, new_scc, x)
scc.append(new_scc)
return scc
if __name__ == "__main__":
it = read_gen('ctc.in')
n, m = next(it), next(it)
g = {x: [] for x in range(1, n + 1)}
gt = {x: [] for x in range(1, n + 1)}
for _ in range(m):
x, y = next(it), next(it)
g[x].append(y)
gt[y].append(x)
scc = solve(g, gt, n)
with open('ctc.out', 'wt') as fout:
fout.write('{}\n'.format(len(scc)))
for scc_comp in scc:
for node in scc_comp:
fout.write('{} '.format(node))
fout.write('\n')