Cod sursa(job #2930166)

Utilizator NCT127Cristina NCT127 Data 27 octombrie 2022 17:05:32
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 2.74 kb
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)