Sakshi and Art in Graph Theory

#1

For this problem my assumption is we need to calculate the edges required to make connection between althe connected components, and used BFS to count the connected components. Not sure whether the problem is in logic or in implementation part. Code is present at https://ide.codingblocks.com/s/183785.

#2

Just give me 10 min i`ll help you out.

#3

@tisandas2011
This is a problem of Euler Path. 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.

#4

Thanks for the solution.