devbelly

문제 https://www.acmicpc.net/problem/11097 알고리즘 SCC 풀이 처음에 문제만 읽어서는 SCC라는 것을 알아채기가 힘들었던 문제입니다. 감이 잡히지 않으므로 2번 예제를 직접 그려보도록 합시다. 그림을 그려본다면 답에 해당하는 간선이 두 가지 종류임을 알 수 있습니다. 첫 번째는 하나의 SCC에서 다른 SCC를 잇는 외부 간선입니다. 두 번째는 각각의 SCC내부를 잇는 내부간선입니다. 이제 각각의 처리방법에 대해 생각해봅시다. SCC알고리즘의 작동방식을 생각해본다면 하나의 컴포넌트로 묶을 때 스택에서 차례대로 하나씩 꺼낸 후 묶는 것을 알 수 있습니다. 즉 스택에서 연속된 값은 서로를 잇는 내부 간선들임을 알 수 있습니다. 즉 스택에서 꺼내며 $sccid$를 부여 할 때 내..