순환 그래프에서 DAG의 LCA에 대한 솔루션을 적용 하시겠습니까?

Question

내 질문에 대한 답이 분명한 것 같아서 분명히 알 수 있습니다. 어떤 예제에 관해서는 왜 우리가 최저 공통 조상 알고리즘을 실행하는 루프를 가질 수 없는지 이해하지만 DAG의 LCA 솔루션에 대해 작성된 논문을 이해하는 데 문제가 있습니다.

• 당신이 LCA에 대한 해결책 중 하나를 설명 할 수 : 그래서 솔루션의 어떤 부분은 내가 아는 기꺼이하고 감사 할 것이 무엇
  대해 연락 .. 순환 그래프에 그것을 사용에서 우리를 중지 너무 많은 formuls없이 DAGs의 문제?
• 어떤 단계에 cylcles에 문제가 있는지 그리고 그 이유는 무엇입니까? 노드의 내 문제에

, 쌍은 LCA 하나 개의 루프 내부에없는 찾을 수 있습니다, 그래서 나는 그것을 해결하는 방법이있을 것 같아요 .. 미리

Answer 1

문제와을의

감사합니다 사이클은 정의 자체에서 시작됩니다.

u 및 v의 LCA는 z가 u 및 v 및 z로부터 도달 z되도록 노드들의 세트로 정의된다 z'가 u 및 v로부터 도달 z'되도록 다른 노드로부터 도달 할 수 없다.

순환 그래프에는 존재하지 않을 수 있습니다. 주기 1->2->3 두 개의 다른 노드와 가장자리가 있다면 예를 들어, : 4->3 및 5->3, 4 및 5에 대한 LCA (모든 1, 2 및 3 그들 모두에서 연결할 수 있습니다,하지만 그들은 서로도 도달 할 수있는 한)이 없다 .

당신은 u 및 v에서 도달 가능한 모든 노드를 찾을 수있는 다음과 둘 다에서 연결할 수 있지만이 만족하는 다른 노드에서 같은 노드 z가의 확인 (A DFS 또는 뭔가 다른 사용) 조건 (다항식 시간에서 작동합니다).

위의 그림에서와 같이 계산할 수있는 것보다 가장 낮은 공통 조상에 대해 의미있는 정의를 갖는 것이 더 중요합니다.하지만 이와 같은 계산은 가능하지만 두 노드가 같은주기가 아님).