monk-at-the-graph-factory

Our Code Monk recently learnt about Graphs and is very excited!  

He went over to the Graph-making factory to watch some freshly prepared graphs. Incidentally, one of the workers at the factory was ill today, so Monk decided to step in and do her job.  

The Monk's Job is to Identify whether the incoming graph is a tree or not. He is given N, the number of vertices in the graph and the degree of each vertex.

Find if the graph is a tree or not.  

Input:
First line contains an integer N, the number of vertices.
Second line contains N space-separated integers, the degrees of the N vertices.  

Output:
Print "Yes" (without the quotes) if the graph is a tree or "No" (without the quotes) otherwise.  

Constraints:
1 ≤ N ≤ 100
1 ≤ Degreei ≤ 1000

References:
Graphs and Trees

SAMPLE INPUT
3
1 2 1

SAMPLE OUTPUT
Yes

Source: hackerearth | Difficulty: EASY
Tags: Tree algorithms

Graph algorithms


Solutions:
nodes = input()
edges = sum([int(x) for x in input().split(" ")])/2
if edges == int(nodes) - 1:
	print("Yes")
else:
	print("No")


n=eval(input())
arr=list(map(int,input().split()))
count=0
flag=0
for item in arr:
	count=count+item
	if item <1:
		flag=1
		break
final=count/2

if final!=n-1:
	flag=1
	
if flag:
	print("No")
else:
	print("Yes")
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
n = eval(input())
degrees = list(map(int, input().strip().split()))
if sum(degrees) == 2 * n - 2:
	print("Yes")
else:
	print("No")


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
n = int(input())
l = list(map(int,input().split()))
ans = sum(l)
if ans == 2*(n-1):
	print("Yes")
else:
	print("No")


n=int(input())
arr=list(map(int,input().split()))
degsum=sum(arr)
if degsum == 2*n-2:print('Yes')
else:print('No')


c = eval(input())
vlist = sorted(map(int, input().split()), reverse=True)	# read and sort the degrees in descending order

def walk(c, vlist):
	for i in range(0, c-1):
		v = vlist[i]

		'''if v == 1:
			if c == 2:
				if vlist[i+1] == 1:	# special case: "1 1"
					vlist = [0, 0]
				return'''

		if v == 0:
			return	

		if vlist[i+1] > 0:	# possibly connect to the vertex which will in turn connect to more vertices, thus, helping us walk the tree
			vlist[i+1] -= 1
			v -= 1

		for j in range(i+2, c):		# consume leaf vertices
			if vlist[j] == 1:
				vlist[j] = 0
				v -= 1
			if v == 0:
				break
	
		vlist[i] = v

walk(c, vlist)

if max(vlist) == 0: print('Yes')
else: print('No')



n = int(input())
a = list(map(int,input().split()))
sum = 0
for i in range(len(a)):
	sum = sum + a[i]
if sum/2 == len(a)-1:
	print("Yes")
else:
	print("No")


N      = int(input())
degree = [int(x) for x in input().split()]
if sum(degree)/2 == N-1:
	print("Yes")
else:
	print("No")


n = int(input())
l = list(map(int, input().split()))
ans = sum(l)
if ans == 2*(n-1):
	print("Yes")
else:
	print("No")



n=int(input())
d=list(map(int,input().strip().split(' ')))
s=0
for x in d:
	s+=x
if s/2 == n-1:
	print('Yes')
else:
	print('No')


nodes = input()
edges = sum([int(x) for x in input().split(" ")])/2
if edges == int(nodes) - 1:
	print("Yes")
else:
	print("No")


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def is_tree(s,n):
	return s==2*(n-1)
n=int(input())
l=input()
l=l.split()
s=0
for x in l:
	s+=int(x)
if is_tree(s,n):
	print("Yes")
else:
	print("No")


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
n = int(input())
l = list(map(int,input().split()))
#print n
#print l
ans = sum(l)
if ans == 2*(n-1):
	print("Yes")
else:
	print("No")


v=eval(input())
deg=input().split()
sum=0
for i in deg:
	sum+=int(i)
if(sum==2*(v-1)):
	print("Yes")
else:
	print("No")


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
n=int(input())

a=list(map(int,input().split()))

if (sum(a)/float(2)==n-1):
	print("Yes")
else:
	print("No")
	


n = int(input())
l = list(map(int, input().split()))
ans = sum(l)
if ans == 2*(n-1):
	print("Yes")
else:
	print("No")



r = int(input())
list = []
x = input()
list = x.split()

sum = 0
for i in list:
	sum += int(i)

if (2*(r-1)) ==  sum:
	print("Yes")
else:
	print("No")


n = int(input())
l = list(map(int, input().split()))
ans = sum(l)
if ans == 2*(n-1):
	print("Yes")
else:
	print("No")



c = eval(input())
vlist = sorted(map(int, input().split()), reverse=True)	# read and sort the degrees in descending order

def walk(c, vlist):
	for i in range(0, c-1):
		v = vlist[i]

		if v == 0:
			return	

		if vlist[i+1] > 0:	# possibly connect to the vertex which will in turn connect to more vertices, thus, helping us walk the tree
			vlist[i+1] -= 1
			v -= 1

		for j in range(i+2, c):		# consume leaf vertices
			if vlist[j] == 1:
				vlist[j] = 0
				v -= 1
			if v == 0:
				break
	
		vlist[i] = v

walk(c, vlist)

if max(vlist) == 0: print('Yes')
else: print('No')



N=int(input())
ans=sum(x for x in map(int,input().split()))
if ans==2*(N-1):
	print('Yes')
else:
	print('No')