유니온 find 방법을 이용하면, 정점과 간선의 정보가 주어졌을 때, 그 안에서 사이클이 발생하는지 아닌지를 알 수 있다.
Ex) 정점의 개수를 n개 입력받고 간선의 개수 m개 입력 받겠다.
이 그래프에서 싸이클이 발생하는지, 아닌지를 union find 방법을 통해 확인하시오
입력
# n, m
6 4
# edge
A B
B C
D E
A D
C D
출력 : 싸이클 발생
'Game AI & Unity > concepts' 카테고리의 다른 글
| [Floyd Warshall 알고리즘] 시작점 X, 가중치 양수X 일 때 (0) | 2024.03.04 |
|---|---|
| [우선순위 큐 (Priority Queue)] (0) | 2024.03.04 |
| [최소 신장 트리 MST(Minimum Spanning Tree)] 최소 비용으로 정점 연결시키기 (0) | 2024.02.23 |
| [Two Pointer] 탐색구간이 정해져있지 않을 때, 구간 합 구하기 (0) | 2024.02.23 |
| [Sliding Window] 탐색구간이 정해져 있을 때, 구간합 구하기 (0) | 2024.02.23 |