그래프 통과

-2

n 명 P1 인 파티에서. . . , Pn, 특정 쌍의 개인은 서로 서있을 수 없습니다. 그러한 쌍의 목록이 주어지면 n 명을 두 그룹으로 나눌 수 있는지 결정합니다. 두 그룹의 모든 사람들 이 우호적 인 관계에 있습니다. 즉, 서로 설 수 있습니다.그래프 통과

출처

2014-11-04 prashanth tv

이것은 문제 설정 질문처럼 보입니다. 지금까지 뭐 해봤 어? – templatetypedef

Grammatically, 이것도 전혀 문제가 아닌 것처럼 보입니다 ... – misberner

네, 인터뷰에서 나에게 질문하는 문제입니다. 나는 그것이 그래프 탐색을 사용하여 완료되어야한다는 것을 알고있다. 그러나 나는 그것을 해결하는 방법에 대한 어떤 생각도 갖고 있지 않다. –

하나의 무력한 해결책은 n/2 명을 선택할 수있는 모든 가능한 조합을 찾은 다음 그룹의 모든 사람이 우호적인지 확인하는 것입니다. 그렇다면 나머지 절반의 모든 사람도 확인해야합니다. 양측이 행복하다면 해결책을 찾았습니다. 그렇지 않으면 다음 조합으로 이동하십시오. 분명히 이상적인 솔루션은 아니지만 결정 론적으로 작동합니다. 일반적으로 인터뷰에서, 더 좋은 아이디어를 얻고 반복하는 것으로 시작하는 것이 가장 좋습니다.

보다 정교한 솔루션은 complement graph을 계산 한 다음 양방향이 아닌 모든 에지를 제거하고 임의의 노드를 선택하여 시작하여 depth-first search을 사용하여 그룹 1에있는 모든 노드를 표시합니다. 그런 다음 표시되지 않은 노드를 선택하고 그룹 2에서 발견 된 모든 노드를 표시하십시오. 표시되지 않은 노드가 남아 있으면 개인을 우호적 인 두 그룹으로 나눌 수 없습니다.

출처

2014-11-04 16:50:28 b4hand

사람들의 쌍이 같은 그룹에 속할 수 없다는 G가 그들 사이에 가장자리를 가지고 있다고 가정합니다. 이 G에서 DFS를 사용하고 Group1을 s로, Group2를 후속으로, Group2 ...를 그룹으로 설정하십시오. 우리가 끝낼 수 있다면, 우리는 그것을 발견 할 것입니다, 그렇지 않으면 우리가 그들을 분할 할 수 없다는 것을 의미하는 충돌이 있습니다. 문제가 제기 될 때 두 그룹으로

출처

2014-11-06 19:02:18 Bill

그래프가 연결되어 있지 않으면이 알고리즘이 그룹을 찾을 것이라고 생각하지 않는다. 예를 들어 X가 싫다면 Y와 Z는 W를 싫어합니다. 유효한 해는 {X, W}와 {Y, Z}입니다. – b4hand

그래프 통과

답변

관련 문제