Cod sursa(job #2929170)

Utilizator ctimburCristina T ctimbur Data 24 octombrie 2022 23:50:54
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.36 kb
# stochez intr-un vector parcugerea in postordine a grafului.
# parcurg vectorul de la coada si aleg cate un nod nevizitat.
# fac o parcurgere dfs in graful transpus avand ca nod de inceput nodul de mai sus.
# nodurile vizitate mai sus sunt elemente al unei componexe tare conexe din graf.
# complexitate O(N + M)
def dfs(node):
	global nr
	visited[node] = True
	for next_node in graph[node]:
		if not visited[next_node]:
			dfs(next_node)
	nr += 1
	postordine[nr] = node

def dfs_transpus(node):
	global count
	visited[node] = True
	ctc[count].append(node)
	for next_node in transpus[node]:
		if not visited[next_node]:
			dfs_transpus(next_node)

fin = open("ctc.in", 'r')
n, m = [int(_) for _ in fin.readline().strip().split()]
graph = [[] for _ in range(n+1)]
transpus = [[] for _ in range(n+1)]
ctc = [[] for _ in range(n+1)]
visited = [False] * (n+1)
postordine = [0] * (10000)
nr = 0
count = 0

for i in range(1, m+1):
	x, y = [int(_) for _ in fin.readline().strip().split()]
	graph[x].append(y)
	transpus[y].append(x)

for i in range(1, n+1):
	if visited[i] == 0:
		dfs(i)
visited = [False] * (n+1)
for i in range(nr, 0, -1):
	if visited[postordine[i]] == 0:
		count += 1
		dfs_transpus(postordine[i])
with open('ctc.out', 'w') as fout:
	fout.write(str(count) + "\n")
	for i in range(1, count+1):
		for j in range(len(ctc[i])):
			fout.write(str(ctc[i][j]) + " ")
		fout.write("\n")