그래프에 사이클이 있는지 확인하는방법

dfs(stack)를 이용하여 그래프에서 사이클이 있는지 확인할 수 있다.

이때 그래프가 유향일때와 무향일때 방법이 각각 다르다.

​

1. 무향그래프

(1) stack

#싸이클인지 확인
def isCycle(L):
    visitedN=[]
    myL=list(L)
    stack=deque([myL[0][0]])    
    while stack:
        nowN=stack.pop()
        #싸이클인지 확인 
        if nowN in stack: #(if nowN in visitedN도 된다!)
            return True
        for i in myL:
            if nowN in i:

                if nowN==i[0]:
                    other=i[1]
                else:
                    other=i[0]
                if other not in visitedN:
                    stack.append(other)
        visitedN.append(nowN)
    return False

싸이클이 있을땐 stack에는 이미 있지만 아직 visited는 되어지지않은 노드가 stack에 또 들어간다.

따라서 이미 stack에 있는 노드가 또 들어가는 경우를 찾아 싸이클인지 확인한다.

​

참고 : https://youtu.be/-rcHMKIBo1E?list=PLVNY1HnUlO25sSWDr7CzVvkOF3bUgkiQQ

 

(2) union-find

속도가 빠르다.

참고문제 : [boj]1197 최소스패닝트리

sosoeasy.tistory.com/47

[백준]1197 최소스패닝트리

 

 

2. 유향그래프

2개의 리스트로 문제를 해결할 수 있다.

하나는 흔히 탐색할때 쓰는 visited리스트이고, 하나는 노드의 탐색이 완전히 끝났을때(해당 노드에서 갈 수 있는 모든 노드들에 방문이 끝마쳤을때) 쓰는 fin리스트이다.

(1) visited리스트 : 노드 node가 dfs로 들어오면 바로 1로 바꿔주고(visited[node]=1)

(2) fin리스트 : 해당 재귀에서 탐색이 종료되었을 때 맨 마지막줄에 1로 바꿔준다(fin[node]=1)

​

ex) [백준]9466 텀프로젝트

from collections import deque
import sys
sys.setrecursionlimit(1000000)

def dfs(node):
    global cnt
    visited[node]=1
    next=graph[node]
    # 다음노드가 방문이 안되였으면 방문해
    if not visited[next]:
        dfs(next)
    # 다음노드가 방문이 되었는데 끝나진않았으면 사이클
    elif not fin[next]:
        tempNode=next
        while(1):
            cnt+=1
            tempNode=graph[tempNode]
            if tempNode==next:
                break
    fin[node]=1

T=int(input())
for t in range(T):
    n=int(sys.stdin.readline().rstrip())
    L=[0]+list(map(int,sys.stdin.readline().rstrip().split()))
    cnt=0

    # 그래프만들기
    graph={}
    for i in range(1,n+1):
        graph[i]=L[i]

    #싸이클확인
    visited=[0 for _ in range(n+1)]
    fin=[0 for _ in range(n+1)]

    for i in range(1,n+1):
        if visited[i]==0:
            dfs(i)
    print(n-cnt)