https://www.acmicpc.net/problem/10891
정점 선인장의 정의에 대해서는 해당 문제에 나와있습니다.
이중 연결 요소를 이용합니다.
그래프의 모든 정점을 이중 연결 요소로 묶어버리면 3가지 유형으로 구분할 수 있습니다.
- 정점이 두 개인 BCC (단절선)
- 단순 사이클
- 단순 사이클이 아닌 사이클
우선 단절선은 단순 사이클에 해당되지 않으므로 무시해주면 됩니다. edge가 한 개 담긴 이중 연결 요소를 만나면 continue하는 식으로 구현하면 됩니다.
단순 사이클의 경우, 문제에서 나온 것처럼 하나까지만 허용해 줍시다.
사이클이면서 단순 사이클이 아닌 경우, 존재만으로 선인장을 만들 수 없습니다. 단순 사이클은 정점의 개수와 간선의 개수가 같다는 특징이 있습니다. 위의 그림에서도 간선 (2, 3)이 없다면 단순 사이클의 조건을 만족합니다.
그러므로 하나의 정점에 대해서 간선의 개수가 3개 이상인 이중 연결 요소가 최대 한 개이면서, 해당 이중 연결 요소의 간선의 개수와 정점의 개수가 동일한지 확인하면 정점 선인장을 판별할 수 있습니다.
Reference
'정리 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 이분매칭 (0) | 2023.03.20 |
|---|---|
| [알고리즘] 쾨닉의 정리 (Kőnig's theorem) (0) | 2023.02.27 |
| [알고리즘] 마나허 (Manacher) (0) | 2023.02.26 |
| [알고리즘] KMP (0) | 2023.02.05 |
| [알고리즘] 이분 탐색 (Binary Search) (0) | 2023.01.15 |
