Cod sursa(job #2795790)

Utilizator NSA-16Neacsu-Tranciuc Sasa-Andrei NSA-16 Data 6 noiembrie 2021 23:36:38
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.24 kb
import sys
sys.setrecursionlimit(10 ** 6)
nid = 0
def CTC(file, file2):
    import collections
    f = open(file, "r")
    g = open(file2, "w")
    n, m = [int(n) for n in f.readline().split()]
    d = [[] for _ in range(n + 1)]
    for i in range(m):
        n1, n2 = [int(n) for n in f.readline().split()]
        d[n1].append(n2)
    ids = (n+1)*[0]
    lowlink = (n+1)*[0]
    ctc = []
    stack = collections.deque()
    onstack = (n+1)*[False]
    def DFS(n):
        global nid
        nid += 1
        ids[n] = nid
        lowlink[n] = nid
        stack.append(n)
        onstack[n] = True
        for i in d[n]:
            if ids[i] == 0:
                DFS(i)
                lowlink[n] = min(lowlink[n], lowlink[i])
            elif onstack[i]:
                lowlink[n] = min(lowlink[n], ids[i])
        if lowlink[n] == ids[n]:
            k = stack.pop()
            c = [k]
            while k != n:
                k = stack.pop()
                c.append(k)
            ctc.append(c)
    for i in range(1, n + 1):
        if ids[i] == 0:
            DFS(i)
    g.write(str(len(ctc)))
    for c in ctc:
        g.write('\n'+" ".join(str(n) for n in c))
    f.close()
    g.close()
CTC("ctc.in", "ctc.out")