Pagini recente » Cod sursa (job #791827) | Cod sursa (job #1323696) | Cod sursa (job #2873303) | Cod sursa (job #446356) | Cod sursa (job #2929170)
# 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")