[일반] E 풀이 SCC 맞음?

[캐티(tae826)]

시팔 100줄 넘어가는 코드 오랜만에 짜보는데 그 마저도 못 맞췄어

[익명(221.147)]

SCC로 지지고 볶다가 BFS인거 깨닫고 오열함

[캐티(tae826)]

아 그러게 SCC만 안하고 내가 한 풀이 그대로 하면 AC였네 시발..

[익명(221.147)]

대충 directed graph로 만들고 나서 각 정점이 세가지 경우로 나뉘잖아 draw, 선공, 후공 위상정렬하듯이 reverse graph에서 BFS하면 됨 선공이 이기는 정점은 바로 정해지니까 여기서부터 시작하면서 정점들 분류하면됨

[캐티(tae826)]

사이클 있으면 위상정렬 안되니까 사이클 지우는 SCC 하고 개지랄했는데 생각해보니 위상정렬이 아니라 위상정렬 스러운 BFS 였음..

[익명(182.231)]

근데 그래프 만들 때 시간초과 안나나요? n이 20만개던데 간선의 최대개수 어케계산함? - dc App

[캐티(tae826)]

간선이 N이 되는 느낌임. 노드는 52^3 개가 생기고 A 라는 문자열은 A의 앞 -> A의 뒤 이런 식으로 연결해주는 간선 만드는 식으로

[김해 청년(119.192)]

그냥 위상정렬로 보고 사이클 찾아도됨 - dc App