Pagini recente » Cod sursa (job #1888441) | Cod sursa (job #1777609) | Cod sursa (job #2255649) | Cod sursa (job #3225238) | Cod sursa (job #2930166)
from operator import truediv
with open("ctc.in","r") as f:
# N,M=[int(x) for x in input.split()]
N,M=[int(x) for x in f.readline().split()]
graf=[]
for line in f:
# print("dati muchia:")
linie=[int(nod) for nod in line.split()]
graf.append(linie)
print(graf)
adj_list={}
for muchie in graf:
# print(muchie[0],muchie[1])
if muchie[0] not in adj_list.keys():
adj_list[muchie[0]]=list()
if muchie[1] not in adj_list.keys():
adj_list[muchie[1]]=list()
if muchie[1] not in adj_list[muchie[0]]:
adj_list[muchie[0]].append(muchie[1])
# print(adj_list)
stk=[]
low=[-1 for i in range(N+1)]
ids=[-1 for i in range(N+1)]
sccs=[]
onStack=[False for i in range(N+1)]
id=0
sccCount=0
news=[]
def dfs(node,low,ids,onStack,stk):
global id
global sccCount
stk.append(node)
onStack[node]=True
ids[node]=low[node]=id
id=id+1
for nod in adj_list[node]:
if ids[nod]==-1:
dfs(nod,low,ids,onStack,stk)
low[node]=min(low[node],low[nod])
if onStack[nod]:
low[node]=min(low[node],ids[nod])
if(ids[node]==low[node]):
# print("scc: ")
top=None
new=[]
while top!=node:
top=stk.pop()
new.append(str(top))
onStack[top]=False
new.sort()
sccCount+=1
news.append(new)
# print(*new,sep=' ')
# print()
for i in range(1,N+1):
if ids[i]==-1:
dfs(i,low,ids,onStack,stk)
g=open("ctc.out","w")
g.write(str(sccCount)+"\n")
for list in news:
for cheie in list:
g.write(str(cheie)+" ")
g.write("\n")
# print(news)
# print(sccCount)
# id=0
# sccCount=0
# sccs=list()
# ids=[0 for i in range(N)]
# low=[0 for i in range(N)]
# onStack=[False for i in range(N)]
# stack=list()
# for i in range(N):
# ids[i]=UNVISITED
# for i in range(N):
# if ids[i]==UNVISITED:
# dfs(i)
# return low
# def dfs(at):
# stack.append(at)
# onStack[at]=True
# ids[at]=low[at] =id+1
# id=id+1
# for nod in adj_list[at]:
# if ids[nod]==UNVISITED:
# dfs(nod)
# if onStack[nod]:
# low[at]=min(low[at],low[nod])
# if(ids[at]==low[at]):
# while True:
# varf=stack.pop()
# onStack[varf]=False
# sccs[varf]=sccCount
# if varf == at:
# break
# sccCount+=1
# print(sccCount)