Cod sursa(job #3374172)

Utilizator mateivoican2006@gmail.comVoican Matei [email protected] Data 8 noiembrie 2026 19:54:45
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.29 kb
def main():
    d = open("ctc.in", "rb").read().split()
    n, m = int(d[0]), int(d[1])
    g = [[] for _ in range(n + 1)]
    gt = [[] for _ in range(n + 1)]
    for i in range(m):
        x, y = int(d[2 + 2*i]), int(d[3 + 2*i])
        g[x].append(y)
        gt[y].append(x)

    viz = [False] * (n + 1)
    it = [0] * (n + 1)
    ordine = []
    for s in range(1, n + 1):
        if viz[s]:
            continue
        viz[s] = True
        st = [s]
        while st:
            v = st[-1]
            if it[v] < len(g[v]):
                u = g[v][it[v]]
                it[v] += 1
                if not viz[u]:
                    viz[u] = True
                    st.append(u)
            else:
                st.pop()
                ordine.append(v)

    comp = [0] * (n + 1)
    rez = []
    for s in reversed(ordine):
        if comp[s]:
            continue
        comp[s] = len(rez) + 1
        grup = [s]
        st = [s]
        while st:
            v = st.pop()
            for u in gt[v]:
                if not comp[u]:
                    comp[u] = comp[s]
                    grup.append(u)
                    st.append(u)
        rez.append(grup)

    with open("ctc.out", "w") as f:
        f.write(str(len(rez)) + "\n")
        f.write("\n".join(" ".join(map(str, c)) for c in rez) + "\n")

main()