You are not logged in. Please login at www.codechef.com to post your questions!

×

Help needed for solving this problem based on graph

 0 Given am array of N integers is it possible to design a simple graph of N vertices?. A graph considered simple if it has no self-loop r multi-edges. The condition is that each element of array should be used exactly once for degrees of vertices of the graph. Print Yes if graph can be designed other wise no. INPUT A single integer T, in the first line, denoting the no. of test cases. For each test case first line is a single integer N, denoting the no. of elements of an array A. The second line contains N space separated integers denoting the elements of an array. OUTPUT For each test case print "YES" or "NO" without quotes. SAMPLE INPUT 3 2 1 1 3 1 2 1 3 1 1 1 SAMPLE OUTPUT YES YES NO asked 13 May '17, 11:57 1★arpit728 683●15●63 accept rate: 10% I'll give a hint for this problem :) For any graph G, SUM(Degree of each node) = 2 x Edges. Using this formula, you get the edges. So you have V,E. Is it possible to draw a Graph with V vertex and E edges, satisfying your constraints. (14 May '17, 16:07)

 0 Please write the problem clearly. What does each element of the array signify? answered 13 May '17, 18:37 4★senbihan 16●2 accept rate: 16% @senbihan It is the degree of each vertex. (13 May '17, 19:34) arpit7281★ @senbihan I have updated the question look at it once more. Tell me if further clarification is needed. (13 May '17, 19:52) arpit7281★
 0 I think this can be solved as follows : Since each element a[i] denotes the degree of the ith vertex we can say that the value of any a[i] can be at most n-1 Secondly, we need to make sure that the sum of all elements in the array (i.e sum of all degrees) is a even number If the above 2 conditions are met, then print YES, otherwise print NO answered 14 May '17, 01:45 1●1 accept rate: 0% @ronakchauhan How to deal with multi-edges. I think the approach which you proposed will not be able to handle multi-edges. (14 May '17, 08:16) arpit7281★
 0 The question clearly stated that the graph should be a simple graph meaning no multi-edges and hence the 1st condition is valid. If u still have doubts about it, try drawing a simple graph where you keep the degree of a vertex > |V|-1. (U will end up with a multigraph) Edit : my solution in code here answered 14 May '17, 10:30 1●1 accept rate: 0%
 0 what you said is wrong,for example consider the following case 1 4 3 3 1 1 For this input your code will print YES,but the answer is no edges will be like this 1 2 1 3 1 4 2 2 There is a self loop for node 2 and hence answer is NO answered 15 May '17, 00:01 1.7k●2●10 accept rate: 14% @hruday968 What would be the correct way then. (16 May '17, 08:29) arpit7281★
 0 Ohh i get it @hruday968, thanks for pointing out! After some googling I found that this problem is the graph realization problem with slight variation. It can be solved using Erdős–Gallai theorem. One way to solve this would be to sort the array in descending order and then apply the theorem answered 15 May '17, 06:37 1●1 accept rate: 0%
 -1 Everyone should know the programming language in every sense of knowledge.wedding photography Kerala and the team like this article so much. answered 15 May '17, 14:22 0★wedphoto -1 accept rate: 0%
 toggle preview community wiki:
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• link:[text](http://url.com/ "title")
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,650
×1,197

question asked: 13 May '17, 11:57

question was seen: 1,107 times

last updated: 16 May '17, 08:29