devbelly

문제 https://www.acmicpc.net/problem/1108 알고리즘 SCC 풀이 점수가 무한대로 늘어나는 것을 방지하기 위해 두 정점에 대해 직간접적 연결이 없을 때에만 점수를 더해준다고 합니다. 직간접 연결을 확인하려면 그래프에서 사이클을 확인해야 하고 사이클을 확인하는 알고리즘인 SCC를 떠올릴 수 있습니다. SCC알고리즘 사용 이후, 모든 간선을 검사하며 두 정점의 $sccid$가 다르다면 $sccadj$에 실제 간선을 추가해줍시다. 이 이유는 하나의 SCC로 묶인 정점들끼리도 점수가 다를 수 있기 때문입니다. 단, $cache$를 갱신하는 과정은 위상정렬상 앞에 있는 순서부터 뒤에 있는 순서로 갱신해나가야 하므로, vector형태를 사용한 것에 주목합시다. 예를 들어 scc_adj[a..