Cod sursa(job #3335242)

Utilizator stefan_15Salcianu Stefan Alexandru stefan_15 Data 22 ianuarie 2026 00:48:16
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.24 kb


import sys
sys.setrecursionlimit(200000)


def Kosaraju():
    sv=[]
    def df1(start):
        s1.add(start)
        for el in adj[start]:
            if el not in s1:
                df1(el)
        sv.append(start)
    for i in range(1, n+1):
        if i not in s1:
            df1(i)
    def df2(start, cct):
        s2.add(start)
        cct.append(start)
        for el in adj_rev[start]:
            if el not in s2:
                df2(el, cct)
    sol=[]
    while sv:
        cr= sv.pop()
        if cr not in s2:
            comonenta=[]
            df2(cr,comonenta)
            sol.append(comonenta)
    return sol

if __name__ == "__main__":
    with open ("ctc.in","r") as f:
        data=f.read().split()
    iterator= iter(data)
    n= int(next(iterator))
    m= int(next(iterator))
    adj=[[] for i in range(n+1)]
    adj_rev=[[] for i in range(n+1)]
    for i in range (m):
        x= int(next(iterator))
        y= int(next(iterator))
        adj[x].append(y)
        adj_rev[y].append(x)
  
    s1=set()
    s2=set()
    rez = Kosaraju()
    with open("ctc.out","w") as f:
        print(len(rez),file=f)
        for el in rez:
            print (*el, file= f)