Cod sursa(job #2929154)

Utilizator bunicul_hackerFlavian bunicul_hacker Data 24 octombrie 2022 21:57:09
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.5 kb
#https://www.infoarena.ro/problema/ctc
import pprint as pp

f = open("ctc.in", "r")
g = open("ctc.out", "w")

l = f.readlines()

#scoatem (n,m) si muchiile
l = [x.split() for x in l]
l = [list(map(int, x)) for x in l]

n, m = l[0]
vertices = l[1:]

#intializam culorile varfurilor cu alb
color = ['white' for _ in range(n)]

lAdc = {x: [] for x in range(1, n + 1)}

for pair in vertices:
    lAdc[pair[0]].append(pair[1])

tNode = [0 for _ in range(n)]

tm = 0
stack = []


def DFS(x):
    global tm
    tm += 1
    color[x - 1] = 'grey'
    for vecin in lAdc[x]:
        if color[vecin - 1] == 'white':
            DFS(vecin)
    color[x - 1] = 'black'
    tm += 1
    tNode[x - 1] = tm
    stack.insert(0, x)


for x in range(n):
    if color[x] == 'white':
        DFS(x + 1)

def tGraph(pList):
    tGraphList = {x + 1 : [] for x in range(n)}
    for key in lAdc:
        for node in lAdc[key]:
            tGraphList[node].append(key)
    
    return tGraphList


color = ['white' for _ in range(n)]

nrCompConxe = 0
sol = []
auxList = []

tGraphList = tGraph(lAdc)

def DFS2(x):
    color[x - 1] = 'grey'
    for vecin in tGraphList[x]:
        if color[vecin - 1] == 'white':
            DFS2(vecin)
    color[x - 1] = 'black'
    auxList.append(x)

for x in range(n):
    if color[x - 1] == 'white':
        DFS2(stack[x])
        sol.append(auxList)
        nrCompConxe += 1
        auxList = []

print(nrCompConxe)
for cc in sol:
    print(cc)