SCC
ganghe74 opened this issue · 5 comments
ganghe74 commented
Strongly Connected Component
강한결합요소
ganghe74 commented
어... tarjan 알고리즘을 보고 있는데 구현이 매우 햇갈린다...
- 원본 그래프
- DFS 스패닝 트리
- SCC 로 구성된 DAG
.....
....
....
그래프 3개를 한문제에서 나타내야 한다! WOW!
ganghe74 commented
SCC DAG 와 관련된 변수에 접두사 s를 반드시 붙여주고.... 비교하는게 같은 그래프에서의 값인지 확인을 잘 하자.
코드 주석에도 넣을 예정.
ganghe74 commented
일단 tarjan 알고리즘을 정리하는 중인데, 사소한 부분들에서 구현을 어떻게 할지 고민중이다.
정점 번호를 0부터 시작할지 1부터 시작할지, scc 배열의 크기를 문제의 정점 개수의 상한으로 할것인지, 아니면 실제 존재하는 scc들을 추가해나갈것인지..
코드길이를 줄이려다보니깐 이런데서 고민이 많이된다. 참고할만한 좋은 짧은코드가 없을까? 🤔