무향/방향 그래프 내 Cycle 판별

1. 무향 그래프 내 Cycle 판별

- 서로소 집합 알고리즘을 사용한다.

- 모든 edge에 대해 두 node의 부모가 같다면, cycle이 존재. 두 node의 부모가 다르다면, union 진행.

v, e = map(int, input().split())
edges = []
for _ in range(e):
    edges.append(list(map(int, input().split())))

parent = [0] * (v+1)
for i in range(v+1):
    parent[i] = i

def find_parent(parent, a):
    if parent[a] == a:
        return a
    else:
        parent[a] = find_parent(parent, parent[a])
        return parent[a]

def union_parent(parent, a, b):
    parent_a = find_parent(parent, a)
    parent_b = find_parent(parent, b)
    if parent_a < parent_b:
        parent[b] = parent_a
    else:
        parent[a] = parent_b

has_Cycle = False
for u, v in edges:
    if find_parent(parent, u) == find_parent(parent, v):
        has_Cycle=True
        break
    else:
        union_parent(parent, u, v)

print('Y') if has_Cycle else print('N')

 

2. 방향 그래프 내 Cycle 판별

- DFS를 통해 판별한다.

- 정점을 3종류로 구분한다.

<방문하지 않은 node, 방문했으나 dfs가 끝나지 않은 node, 방문했고 dfs도 끝난 node>

방문하지 않은 node: 방문 but dfs 안끝남 처리 -> dfs -> 방문 and dfs 끝남 처리

방문했으나 dfs 끝나지 않은 node: cycle임

방문했고 dfs도 끝난 node: 더 볼 필요 없음

N = 7
edges = [(1, 2), (1, 5), (2, 3), (2, 6), (3, 4), (6, 4), (4, 7), (7, 6)]
graph = [[] * (N+1) for _ in range(N+1)]
for u, v in edges:
    graph[u].append(v)

# 0: Not Visited, -1: Visited, dfs not finished, 1: Visited, dfs finished
visited = [0] * (N+1)

def dfs_has_cycle(now):
    if visited[now] == -1:
        return True
    if visited[now] == 1:
        return False
    visited[now] = -1
    for v in graph[now]:
        if dfs_has_cycle(v):
            return True
    visited[now] = 1
    return False