Cod sursa(job #3370924)

Utilizator EmimaCurcan Sara Emima Emima Data 27 octombrie 2026 21:07:14
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 3.5 kb
"""
def listaAdiacenta(m):
    d={}
    for _ in range(m):
        u,v=[int(x) for x in input().split()]
        if u not in d:d[u]=[]
        if v not in d[u]:d[u].append(v)
    return d

def listaGt(d):
    g={}
    for nod in d:
        for vecin in d[nod]:
            if vecin not in g:g[vecin]=[]
            if nod not in g[vecin]:g[vecin].append(nod)
    return g

def dfsG(x,d,viz,stiva):
    viz[x]=1
    if x in d:
        for y in d[x]:
            if viz[y]==-1:
                dfsG(y,d,viz,stiva)
    stiva.append(x)

def dfsGt(x,g,viz):
    viz[x]=2
    if x in g:
        for y in g[x]:
            if viz[y]==1:
                dfsGt(y,g,viz)

n,m=[int(x) for x in input().split()]
d=listaAdiacenta(m)
g=listaGt(d)
viz=[-1]*(n+1)
stiva=[]
for nod in range(1,n+1):
    if viz[nod]==-1:
        dfsG(nod,d,viz,stiva)

tare_conexe=0
while stiva:
    i=stiva.pop()
    if viz[i]==1:
        tare_conexe+=1
        dfsGt(i,g,viz)

print(tare_conexe)
"""

""" 
#planets and kingdoms
import sys
sys.setrecursionlimit(300000)

def listaAdiacenta(m,input_data,idx):
    d={}
    for _ in range(m):
        u=int(input_data[idx])
        v=int(input_data[idx+1])
        idx+=2
        if u not in d:d[u]=[]
        d[u].append(v)
    return d

def listaGt(d):
    g={}
    for nod in d:
        for vecin in d[nod]:
            if vecin not in g:g[vecin]=[]
            if nod not in g[vecin]:g[vecin].append(nod)
    return g

def dfsG(x,d,viz,stiva):
    viz[x]=1
    if x in d:
        for y in d[x]:
            if viz[y]==-1:
                dfsG(y,d,viz,stiva)
    stiva.append(x)

def dfsGt(x,g,viz,label,ans):
    viz[x]=2
    ans[x]=label
    if x in g:
        for y in g[x]:
            if viz[y]==1:
                dfsGt(y,g,viz,label,ans)

n,m=map(int,input().split())
input_data=[]
for _ in range(m):
    input_data.extend(input().split())

d=listaAdiacenta(m,input_data,0)
g=listaGt(d)

viz=[-1]*(n+1)
stiva=[]
for nod in range(1,n+1):
    if viz[nod]==-1:
        dfsG(nod,d,viz,stiva)

ans=[0]*(n+1)
tare_conexe=0
while stiva:
    i=stiva.pop()
    if viz[i]==1:
        tare_conexe+=1
        dfsGt(i,g,viz,tare_conexe,ans)

print(tare_conexe)
print(*(ans[1:]))
"""

import sys
sys.setrecursionlimit(300000)
def listaAdiacenta(m,fisier):
    d={}
    g={}
    for _ in range(m):
        u,v=[int(x) for x in fisier.readline().split()]
        if u not in d:d[u]=[]
        d[u].append(v)
        if v not in g:g[v]=[]
        g[v].append(u)
    return d,g
def dfsG(x,d,viz,stiva):
    viz[x]=1
    if x in d:
        for y in d[x]:
            if viz[y]==-1:
                dfsG(y,d,viz,stiva)
    stiva.append(x)
def dfsGt(x,g,viz,componenta):
    viz[x]=2
    componenta.append(x)
    if x in g:
        for y in g[x]:
            if viz[y]==1:
                dfsGt(y,g,viz,componenta)
file=open('ctc.in','r')
g_out=open('ctc.out','w')
first_line=file.readline()
if not first_line:
    file.close()
    g_out.close()
    sys.exit(0)
n,m=[int(x) for x in first_line.split()]
d,g=listaAdiacenta(m,file)
viz=[-1]*(n+1)
stiva=[]
for nod in range(1,n+1):
    if viz[nod]==-1:
        dfsG(nod,d,viz,stiva)
componente=[]
while stiva:
    i=stiva.pop()
    if viz[i]==1:
        comp=[]
        dfsGt(i,g,viz,comp)
        componente.append(comp)
g_out.write(str(len(componente))+"\n")
for comp in componente:
    g_out.write(" ".join(str(x) for x in comp)+"\n")
file.close()
g_out.close()