Pagini recente » Cod sursa (job #3205835) | Cod sursa (job #2114657) | Rating anaida (anaida) | Cod sursa (job #1922498) | Cod sursa (job #2927874)
import sys
sys.setrecursionlimit(1000001)
f = open("ctc.in")
line = f.readline()
v = line.split()
n = int(v[0]) #nr varfuri
m = int(v[1]) #nr muchii
lista=[]
stv=[]
#construire matrice de adiacenta
def citire_matrice_liste(noduri, muchii, orientat):
l = {}
for i in range(1, noduri + 1):
l[i] = []
for i in range(muchii):
line = f.readline()
v = line.split()
if orientat:
l[int(v[0])].append(int(v[1]))
else:
l[int(v[0])].append(int(v[1]))
l[int(v[1])].append(int(v[0]))
return l
#lista este matricea de adiacenta
lista = citire_matrice_liste(n, m, 1)
#facem dfs grafului G
def Dfs(nod,visited_vertex,lista):
visited_vertex[nod] = 1
global stv
stv.append(nod)
for vecin in lista[nod]:
if visited_vertex[vecin]==0:
Dfs(vecin,visited_vertex,lista)
# introducem intr-o stiva la momentul finalizat (penttu a a obtine o ordine descrescatoare)
def fill_order(nod,visited_vertex, stack):
visited_vertex[nod] = 1
for vecin in lista[nod]:
if visited_vertex[vecin]==0:
fill_order(vecin,visited_vertex, stack)
stack = stack.append(nod)
# facem G^t
def transpose():
g = {}
for i in range(1, n + 1):
g[i] = []
for i in lista:
for j in lista[i]:
g[j].append(i)
return g
#afisam componentele tare conexe
d={}
def print_scc():
global d,stv
nr=0
stack = []
visited_vertex = [0] * (n+1)
for i in range(1, n + 1):
if visited_vertex[i]==0:
fill_order(i,visited_vertex, stack)
gr = transpose()
visited_vertex = [0] * (n + 1)
while stack:
i = stack.pop()
if visited_vertex[i]==0:
nr=nr+1
Dfs(i,visited_vertex,gr)
d[nr]=[]
for i in stv:
d[nr].append(i)
stv=[]
print_scc()
g=open("ctc.out","w")
g.write(str(len(d))+"\n")
for x in d:
for i in d[x]:
g.write(str(i)+" ")
g.write("\n")