Pagini recente » Cod sursa (job #2506792) | Cod sursa (job #2820587) | Cod sursa (job #1624904) | Cod sursa (job #839420) | Cod sursa (job #2929154)
#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)