https://www.acmicpc.net/problem/3682
티어: 플래티넘 2
로직
문제를 바꿔 생각해보면, 주어진 그래프를 딱 하나의 SCC로 만들기 위해 추가해야할 간선의 최소 개수가 정답이 됩니다.
간선의 최소 개수는 indegree가 0인 scc의 수, outdegree가 0인 scc의 수 중 큰 수 입니다.
원래 그래프가 하나의 SCC였다면, 0을 출력하도록 따로 처리해줘야 합니다.
'백준 & 알고리즘' 카테고리의 다른 글
| [파이썬] 백준 1471번 - 사탕 돌리기 (0) | 2023.10.16 |
|---|---|
| [파이썬] 백준 26157번 - 즉흥 여행 (Hard) (0) | 2023.10.16 |
| [파이썬] 백준 4013번 - ATM (0) | 2023.10.13 |
| Top-down DP와 Bottom-up DP의 차이점과 장단점, 쓰는 경우 (1) | 2023.06.23 |
| [파이썬] 백준 1111번 - IQ Test 풀이 (0) | 2023.06.23 |
