I'm confused with the logic

#1

I know that for this question we have to calculate the euler path but I’m confused how are the degrees working and how by using that we will solve this.
code-https://ide.codingblocks.com/s/185517?_ga=2.89787805.780598319.1600270531-1523752193.1557744795
I referred this code and am not sure what line 33 and 35 mean.
Also how by knowing the degree of each node will we know the answer?

#2

and why do we need odd edges?

#3

and we are using euler path so why dont we have in and out times being noted

#4

Can someone please reply

#5

Hey consider this simple case:

graph1
graph11772×808 2.83 KB

although there is only one connected component, still you can’t complete it in one stroke(you need to add atleast one more extra line)

See except for the starting and ending point, all points need to have even degree inorder to complete figure in one stroke(because for every point except start and end, you will go towards it and also leave it) hence if some node has odd degree then eventually you have to reach it by making extra line(note that this extra line again makes the degree of that node even)

#6

In line 33 we have number of odd degrees in temp

In line 35 we will have ans=max(count_cc-1,(total_odd_vertex-1)/2) (count_cc is the number of connected components in the graph)

Logic behind this question is:
Consider this as a graph(lines as edges and points as nodes). We need to add edges, such that there is a Euler Path. Let C1, C2, C3 ,C4 … Ck be connected components of graph. Count the number of vertices(count of the open ends) with odd degree. If there is no vertex with odd degree, in a connected component, consider that there are two open ends, so add two to the count. You can leave atmost two open ends unpaired. That means, the number of pairings that need to be done are the minimum number of edges to be added.

Consider this as a graph(lines as edges and points as nodes). We need to add edges, such that there is a Euler Path . Now, first find the number of odd degrees in all the connected component
If in a connected component
(odd_vertex denotes number of odd degree vertex in the connected components)

  1. no of odd degree <= 2, then do odd_vertex+=2 ( to connect it with other connected component)
  2. no of odd degree >2 then do odd_vertex+=no of odd degree

we are doing this in order to eliminate any vertex with odd degree ( by adding an edge to it) because of we have a vertex with odd degree we can’t draw the graph in a single stroke

we will have ans=max(count_cc-1,(odd_vertex-1)/2) (count_cc is the number of connected components in the graph)

1 Like
#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.