백준 알고리즘 일지 #1

자, 오늘은 무엇을 공부했는가, 

사실 오늘 한건 아니고, SCC라는 테크?닉에 대해 공부를 했다

SCC는 Tarjan's algorithm으로 구현하는 방법을 학습하였다.

대충 말하자면, 트리를 만들고(그래프로? 이건 좀 귀한데) 자기 자신에서 최대로 향할 수 있는 부모 정점이

자신이면 SCC로 스택에서 꺼내는, 뭐 그런 식이다.

SCC의 성질로부터 사이클들을 SCC로 만들고, SCC로 만든 그래프는 사이클이 없는 방향그래프가 된다.

즉, DAG이다.

DAG에 먼짓을 할 수 있냐?

그건 위상정렬이죠. 위상정렬에 뇌가 절여지는 중이다.

과고에 있을 적 cactus를 매우 좋아하는 친구가 있었다.

단절점 / 단절선을 배운 다음 그 유명한 cactus를 보고 싶은 느낌이다.