연결되지 않은 유향 그래프 vertitudes의 최대 서브 세트 크기?

Question

주어진 그래프를 통해 최대 2 개의 버텍스 서브 세트가 지시 된 경로로 연결되지 않도록하는 방법은 무엇입니까?

이 문제 (또는 해결 알고리즘)는 일반적인 이름입니까?

(이 힌트 :. 딜 워스의 정리에 따르면는 "이 문제는 이후의 전이 폐쇄를 계산 DAG의에 포함 체인의 최소 수 실제로 동일하다 따라서이 문제는 이분 그래프의 최대 일치를 줄일 수 있습니다. ")

Answer 1

나는 그것이 연합 찾기 사용 Disjoint-set data structure

의 하위 문제 같아요, 이름을 모르는, 당신은 연결된 모든 그래프를 확인할 수 있습니다.

처음에는 각 노드가 해당 그룹에 있습니다. 모든 노드를 확인하고 모든 직접 자식을 노드의 그룹 루트에 추가하십시오. 이것은 기본 연합 찾기입니다.

그런 다음 가장 큰 부분 집합은 각 그룹의 하나의 버텍스로 구성됩니다.

최악의 경우, 모든 노드가 다른 모든 노드에 연결되어 있으면 모든 노드가 n 번 확인 될 때 ​​O (n²)가됩니다.