Problem setter: panik
Problem Code: NINENINE
Difficulty: Medium-Hard
Prerequisites: Finding Bridges in a graph in linear time, Combinatorics, Inclusion Exlusion Principle…
Explanation:
First of all, you need to calculate the bridges in the graph in linear time, since the graph must remain connected at every step i.e during deletion and insertion.
To find this you can read about it in these links:
1.) G4G
2.) youtube video (I personally found this link better than G4G)
After you have obtained the set of Bridges, you now need to precalculate some things which would later prove to be helpful.
1.)save all the edges of the Graph in an unordered Set. This can be done in nearly Linear time.
2.) For each vertex find the count of vertices connected to it having a particular degree for each kind of available degree. Store this information in a vector of maps which contains this information for each node. This can be done in O(M).
3.) Store the count of edges between vertex of degree x and vertex of degree y for all possible edges available in the graph. Store this information in a map which stores the count of edges between a particular degree x to a particular degree y. This can be done in O(M)
4.) Make a frequency array and find the count of vertices of each particular degree.
Now comes the time to finally start calculating all the possible graphs.
Start Traversing all the edges in Graph.
If the edge is available in the set of bridge edges, then skip this edge
If not,
Temporarily reduce the degree of both the vertices of the edge and reflect this change only in the frequency array. So the count of original degree frequencies reduces by 1 and the new degree frequency increase by 1.
This change would be reverted later.
If the degree of both the vertices is same p= (freq[degree]X(freq[degree]-1))/2 -1
Else p= freq[degree1]*freq[degree2] - 1
Now we need to remove some cases from p to remove the cases where multiple edges occurred in some possible graphs i.e edge already exist in the graph. We also need to add some cases in p because of change in the degree of some vertex due to which count of edges between two particular degrees would change, so some extra cases would be subtracted from p when subtracting those edges which already exist in the graph. This can be done by some observation in the graph
Refer to the solution for better clarity.
Author’s solution: click here
Testers Solution : click here
Bonus question: What if I remove the statement that the graph must be connected at each step and replace it with that the final graph should be connected which means that the graph can disconnect during deletion but later during insertion has to become connected again.
Personally, I was not able to find a solution to this question. Lets discuss this in the comment section. I would seriously like to know the solution to this problem.