Given a set of nodes numbered 1, 2, .. N, and a list of edges, we define an "operation" as removing an existing edge between two vertices and placing it between two other vertices. What is the minimum number of operations needed to connect the graph?
We are given the number of vertices and edges as input, and then we are given the list of edges.
For instance, if there are 2 vertices and 1 edge, and the one edge is (1, 2), then you don't need any operations since you're already done.
On the other hand, if there are 4 vertices and the edges are (1, 2), (1, 3), and (2, 3), then 4 isn't connected, but you can remove any edge and connect it to get 4 with just one operation. So the output is 1.
How can I solve this problem?
I am thinking about finding the number of connected components, and going from there, but I have not been able to make any progress. I am really bad at graph implementations though, and I would really appreciate some sort of help.
Perhaps you can use dsu to detect "redundant" edges and use them to connect two nodes in different SCC's. I have no idea how exactly to implement this though
You should provide the source of problem to get help from anyone
Assuming the graph is undirected with no multiple edges or loops to keep the explanation simple.
First, split the graph into connected components. So every edge and vertex belongs to one connected component. If you have p connected components you will need to add p-1 edges between them to make them connected.
For a connected component with n vertices, the number of edges in it will be >= n-1. Let x be the number of extra edges x=no.edges-(n-1) .So x is the number of edges you can remove from this component while still keeping it connected.
Count the total number of extra edges you have over all connected components; if this is less than p-1 then it is not possible to connect the graph else the answer in p-1