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

×

Help needed for solving this problem based on graph

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

arpit728's gravatar image

2★arpit728
6831456
accept rate: 10%

edited 13 May '17, 19:51

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) codedecode01115★

Please write the problem clearly. What does each element of the array signify?

link

answered 13 May '17, 18:37

senbihan's gravatar image

4★senbihan
162
accept rate: 16%

@senbihan

It is the degree of each vertex.

(13 May '17, 19:34) arpit7282★

@senbihan

I have updated the question look at it once more. Tell me if further clarification is needed.

(13 May '17, 19:52) arpit7282★

I think this can be solved as follows :

  1. 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
  2. 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

link

answered 14 May '17, 01:45

ronakchauhan's gravatar image

3★ronakchauhan
11
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) arpit7282★

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

link

answered 14 May '17, 10:30

ronakchauhan's gravatar image

3★ronakchauhan
11
accept rate: 0%

edited 14 May '17, 10:39

@ronakchauhan

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

link

answered 15 May '17, 00:01

hruday968's gravatar image

4★hruday968
1.7k210
accept rate: 14%

edited 15 May '17, 00:03

@hruday968

What would be the correct way then.

(16 May '17, 08:29) arpit7282★

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

link

answered 15 May '17, 06:37

ronakchauhan's gravatar image

3★ronakchauhan
11
accept rate: 0%

edited 15 May '17, 06:47

-1

Everyone should know the programming language in every sense of knowledge.wedding photography Kerala and the team like this article so much.

link

answered 15 May '17, 14:22

wedphoto's gravatar image

0★wedphoto
-1
accept rate: 0%

toggle preview
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,631
×1,182

question asked: 13 May '17, 11:57

question was seen: 1,048 times

last updated: 16 May '17, 08:29