배열이 그래프를 형성 할 수 있는지 확인하십시오.

Question

[면접 질문] 최근 온라인 인터뷰에서이 질문을 받았습니다. 나는 그것을 풀 수있는 단서가 없었다. 아무도 내가 자바에서 배울 수 있도록이 문제를 해결하는 데 도움 주시기 바랍니다 수 있습니다.

톰은 문제 해결에 매우 좋습니다. 따라서 Tom의 기술을 테스트하기 위해 Jerry는 Tom에게 그래프 문제를 묻습니다. Jerry는 N 정수 중 A 배열 인 Tom을 제공합니다.

그래프는 자체 루프 또는 다중 에지가없는 경우 간단한 그래프입니다.

이제 Jerry는 N 개의 꼭지점의 간단한 그래프를 디자인 할 수 있는지 여부를 묻습니다. 조건은 Tom이 그래프의 정점의 정도에 대해 A의 각 요소를 정확히 한 번 사용해야한다는 것입니다.

이제 Tom은 자신의 그래프를 디자인하는 데 도움을 원합니다. 그래프를 디자인 할 수 있으면 "예"를, 그렇지 않으면 "아니오"(따옴표 제외)를 인쇄하십시오.

입력 첫 번째 줄에있는 단일 정수 T는 테스트 사례의 수를 나타냅니다. 각 테스트 케이스에는 2 개의 라인이 있습니다. 첫 줄 번째 행은 각 테스트 케이스 A.

요소

출력 를 나타내는 N-공간 분리 정수를 갖는 어레이 A의 엘리먼트들의 수를 나타내는, 단일 정수 N 인 인쇄 "YES" 또는 그래프를 디자인 할 수 있는지 여부를 "NO"(따옴표 제외)로 변경하십시오.

제약

1<= T <= 100 
1<= N <= 100 
0<= Element of A <= 5000 

샘플 테스트 케이스

입력

1 
2 
1 1 

출력

YES 

이 테스트 케이스에 대한 설명 , 2 개 정점 간단한 그래프는 각 정점도를 갖는 경우, 설계 될 수있다 1.

입력

2 
3 
1 2 1 
3 
1 1 1 

출력

YES 
NO 

첫 번째 테스트 케이스 설명 , 우리는 간단하게 설계 할 수있다 [1, 2, 1]과 같은 차수 시퀀스를 갖는 3 개의 꼭지점의 그래프. 첫 번째 정점은 차수 1, 두 번째 차수는 2이고 세 번째 정점은 1입니다. 두 번째 테스트 케이스의 경우도 순서가 [1, 1, 1] 인 3 개의 꼭지점에 대한 간단한 그래프를 만들 수 없습니다.

Answer 1

하나의 불필요한 조건은 A의 요소 합이 균일하다는 것입니다. 이는 각 경계 이 인접 목록에서 두 번 계산되기 때문입니다.

다음은 그래프를 구성하거나 적어도 노드 쌍을 '할당'하려고합니다.목록으로 구성되어 있기 때문에 다음 단계에서 정렬하는 것은, 병합 정렬 단계 O (N)에서 수행 될 수 있음을

Sort elements of A in decending order, 
Let the largest (first) element be a, 
Check are element on positions 2 to a+1 larger than 0, 
    If there is a element with value 0 than it is not possible to construct a graph, 
Decrease these a elements by 1 and set first element to 0, 
Repeat process until all elements are 0. 

주 세 분류 부품의 :

• 첫 번째 요소 (0)에 갈 수 있습니다 끝,
• 요소가있는 정렬 된 부분,
• 나머지도 정렬됩니다.