Problem setter: panik Problem Code: NINENINE Difficulty: MediumHard 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: 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 degree of both the vertices is same p= (freq[degree]X(freq[degree]1))/2 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. asked 11 Jan, 18:35

At first, I missed the statement that graph should be connected at each step and thought of the following solution: Make bridge tree of the graph and calculate the answer corresponding to nonbridges as earlier. For bridges (let uv), find the components (nodes in the bridge tree) in which u and v lie. Now we need to calculate the number of nodes with a given degree in the subtree of a node of bridge tree. This can be done using euler tour of the tree which is used for subtree queries. Since degree can be upto M, we can store the nodes for each degree and use binary search to get the count of nodes that belong to the subtree. Here, we do not need to worry about formation of multiple edges since it is a bridge. answered 12 Jan, 18:14
