타잔 알고리즘(SCC:강한 결합 연결) - 파이썬(python)

# strongly connected component
def scc(g,v):
    finished=[False]*(v+1)
    label=[0] # 누적 라벨 : 노드를 한번 방문 할때마다 1씩 증가
    labels=[0]*(v+1) # 고유 라벨 저장
    ans,s=[],[]
    
    
    def _scc(u):
        label[0]+=1
        parent=labels[u]=label[0]
        s.append(u)
        
        for v in g[u]:
            if not labels[v]:
                
                parent=min(parent,_scc(v))
            elif not finished[v]:
                # 방문 했었으나 scc처리가 아직 안된 노드 = 사이클
                parent=min(parent,labels[v])
        if parent==labels[u]:
            # 자기 자신이 사이클 중 가장 먼저 탐색= 루트노드
            scc_set=[]
            while s:
                p=s.pop()
                scc_set.append(p)
                finished[p]=True
                if u==p:
                    break
            ans.append(scc_set)
        return parent
    
    for e in range(1,v+1):
        if not labels[e]:
            _scc(e)
    
    return ans

 

참고

c++:https://blog.naver.com/ndb796/221236952158

파이썬:https://storyofvector7.tistory.com/44

[알고리즘] 강한 연결 요소(2): 타잔 알고리즘