일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- LeetCode
- 밴픽
- Regular Expression
- concurrency
- 43. Multiply Strings
- 715. Range Module
- 컴퓨터의 구조
- 파이썬
- shiba
- attribute
- Class
- iterator
- 프로그래머스
- Convert Sorted List to Binary Search Tree
- Substring with Concatenation of All Words
- Generator
- kaggle
- Protocol
- 315. Count of Smaller Numbers After Self
- Python
- Decorator
- DWG
- t1
- data science
- 시바견
- 운영체제
- Python Implementation
- Python Code
- 109. Convert Sorted List to Binary Search Tree
- 30. Substring with Concatenation of All Words
Archives
- Today
- Total
Scribbling
무향/방향 그래프 내 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
'Computer Science > Algorithms & Data Structures' 카테고리의 다른 글
위상 정렬 (0) | 2021.08.14 |
---|---|
신장 트리, 최소 신장 트리, Kruskal Algorithm (0) | 2021.08.13 |
서로소 집합 알고리즘 (0) | 2021.08.12 |
Python Set 자료형 (0) | 2021.08.11 |
최단 거리 알고리즘 (0) | 2021.08.10 |