https://www.acmicpc.net/problem/26157
티어: 플래티넘 3
로직
하나의 SCC 안에 들어있는 나라들은 서로 자유롭게 이동할 수 있으므로, 하나의 노드로 생각할 수 있습니다.
먼저, 주어진 그래프를 SCC 단위로 분리합니다. 분리된 SCC의 개수가 1개라면 아무데서나 출발해도 됩니다.
indegree가 0인 SCC의 개수가 1개이고, 해당 scc에서 모든 노드를 방문할 수 있으면 해당 scc가 정답이 됩니다.
indegree가 0인 SCC의 개수가 2개 이상이고, 모든 노드를 방문할 수 없다면 정답은 0이 됩니다.
'백준 & 알고리즘' 카테고리의 다른 글
| [파이썬] 백준 1108번 - 검색 엔진 (0) | 2023.10.17 |
|---|---|
| [파이썬] 백준 1471번 - 사탕 돌리기 (0) | 2023.10.16 |
| [파이썬] 백준 3682번 - 동치 증명 (0) | 2023.10.15 |
| [파이썬] 백준 4013번 - ATM (0) | 2023.10.13 |
| Top-down DP와 Bottom-up DP의 차이점과 장단점, 쓰는 경우 (1) | 2023.06.23 |
