Pagini recente » Cod sursa (job #3222648) | Cod sursa (job #428975) | Cod sursa (job #1969962) | Cod sursa (job #1649415) | Cod sursa (job #2928091)
#complexitate O(n+m)
def dfs(node):
global la
global viz1
global queue
if node not in viz1: #prima parcurgerea DFS pe graful initial
viz1.append(node)
queue.append(node) #retin rezultatul pentru a-l folosi la urmatoarea parcurgere dfs pe graful complementar
for vecin in la[node]:
dfs(vecin)
def dfs2(node,ctc):
global la_reversed
global viz2 #parcurg graful complementar, fiecare parcurgere reusita reprezentand o componenta tare conexa
if node not in viz2:
viz2.append(node)
queue.remove(node)
ctc.append(node+1)
for vecin in la_reversed[node]:
dfs2(vecin,ctc)
f = open("ctc.in","r")
n,m= (int(x) for x in f.readline().split())
la = [[] for i in range(n)]
la_reversed = [[] for i in range(n)]
for linie in f:
x,y = (int(a) for a in linie.split())
la[x-1].append(y-1) #lista de adiacenta pentru graful initial
la_reversed[y-1].append(x-1) #lista de adiacenta pentru graful complementar
f.close()
viz1 = []
viz2 = []
queue = []
componente = list()
dfs(la[0][0])
while(queue):
ctc = list()
dfs2(queue[0],ctc) #parcurgere dfs pentru toate nodurile din graful complementar
componente.append(ctc) #retin astfel toate ctc gasite intr-o lista
with open("ctc_out",'w') as f:
f.write(str(len(componente))+"\n")
for i in range(len(componente)):
f.write(str(componente[i])+"\n")