그래프의 사이클 판별

무방향 그래프와 방향 그래프

---

무(無)방향 그래프

• 서로소 집합은 공통 원소가 없는 두 집합을 의미한다.
• find함수는 해당 노드의 root 노드를 찾는 함수이다.
• union은 두 노드가 속한 집합을 합치는 함수이다.
• 만약 root 노드가 같다면, 이는 사이클이 존재함을 의미한다.

def find(x, parent):
    if x != parent[x]:
        parent[x] = find(parent[x], parent)
    return parent[x]

def union(a,b,parent):
    a = find(a, parent)
    b = find(b, parent)
    parent[max(a,b)] = min(a,b)

---

방향 그래프

• 방문 여부를 확인하는 visited, 현재 탐색 경로를 나타내는 stack을 노드의 개수만큼 정의한다.
• 모든 노드에 대해 dfs를 수행한다.
• 해당 노드의 이웃 노드들을 확인하면서, 재귀적 탐색의 결과가 True거나 stack에 이미 있는 경우, 사이클이 존재한다.
• 모든 이웃 노드에 대해 탐색 후 False라면, 사이클이 없으므로 stack에서 해당 노드를 제외한다.

def dfs(node, visited, stack):
    visited[node] = True
    stack[node] = True

    for neighbor in graph[node]:
        if not visited[neighbor]:
            if dfs(neighbor, visited, stack):
                return True
        elif stack[neighbor]:
            return True

    stack[node] = False
    return False

visited = [False] * num_nodes
stack = [False] * num_nodes