scc들에 대해서 in-degree를 재려고 하신 것 같은데
지금 in값이 커지는 기준이 원래 그래프의 간선으로 되어 있습니다.
다시 말하면, 한 scc에서 다른 scc로 가는 (원래 그래프상의) 간선이 여러 개여도 하나로 세야 하는데
다 따로 세기 때문에 topo 벡터가 잘못 만들어집니다.
4013번 - ATM
scc들에 대해서 in-degree를 재려고 하신 것 같은데
지금 in값이 커지는 기준이 원래 그래프의 간선으로 되어 있습니다.
다시 말하면, 한 scc에서 다른 scc로 가는 (원래 그래프상의) 간선이 여러 개여도 하나로 세야 하는데
다 따로 세기 때문에 topo 벡터가 잘못 만들어집니다.
추가로 팁을 드리자면, 코사라주 알고리즘을 쓰면
두 번째 DFS에서 scc들에 번호가 붙여지는 순서가 곧 scc들의 위상정렬된 순서이기 때문에
굳이 다시 안 해줘도 됩니다.
아 맞습니다 처음에 9개짜리로 했다가 2개 뺀 거라서..
댓글을 작성하려면 로그인해야 합니다.
ness9917 1년 전
코사라주 알고리즘을 이용해서 풀어보았는데요,
그래프를 scc그래프로 변환하고,
위상정렬 후에
시작지점이 있는 scc컴포넌트로부터 dp를 이용해서 최댓값을 구했습니다.
게시판 반례들은 모두 통과합니다.
반례 부탁드립니다 ㅠㅠ