rlj1202   3달 전

블로그에 있는 많은 코드들을 보면 자신의 low를 업데이트 할 때 backedge가 아님에도 부모의 dfn으로 자신의 low를 업데이트하고 있습니다. 영문으로 검색하면 부모 여부를 확인하는 코드가 대부분이였구요. low[A] = B 를 "A정점은 B정점에서 우회해서 올 수 있다" 라고 해석한다면... 부모노드까지 보아도 해석에 큰 문제가 없기 때문일까요??

shjgkwo   1달 전

단절점 원리를 생각해보시면,

"어떤 노드 u에 대해, 자기 자식노드에 해당하는 노드들이 백에지를 통하여 u의 부모를 포함한 조상으로 올라갈 방법이 전부 있다면 그 노드가 단절점이 아니다." 

이 원리에 기초하여 생각해봅시다. 우선, 부모노드를 본다는 건 부모노드와 그 자식노드간에 간선이 하나 더 있게 되는건데, 위의 개념은 그러한 모순을 전혀 신경쓰지 않습니다.

부모노드에 몇번이고 갈 수 있다 한들, 그 부모노드를 지워버리면 그렇게 발생한 간선들이 아무런 의미가 없으니까요.

따라서 구현할때는 부모노드를 거르지 않아도 정답이 되는것입니다. 하지만 일반적인 개념에 충실하여 구현한다면 부모노드를 거르는 게 맞지요.

댓글을 작성하려면 로그인해야 합니다.