You are given an integer N and a prime P. Count the number, modulo P, of undirected connected graphs G of N vertices numbered 1 to N that satisfy the following conditions:
There are no self-loops in G. Note that multiple edges are allowed.
For all edges (u,v) in G, if we delete (u,v) from G, G remains connected. In other words, G is edge-biconnected.
For all edges (u,v) in G, if we delete (u,v) from G, G is no longer edge-biconnected. Two graphs are considered different if and only if there exists a pair of distinct vertices (u,v) such that the numbers of edges connecting u and v in the two graphs are different.
N<=50, P<=1e9
Input : Two integers N and P
Output: Print the answer.
If we try to delete an edge, the remaining graph will be a chain after shrinking biconnected components (a cycle if adding it back). We consider solving the problem for every biconnected component and multiplying the answer. In the subproblem there is an additional edge between two vertices, because they can reach each other through the cycle. Using this method repeatedly. Each time taking an edge connected to vertex 1. Then we will get subproblems of the following format: Count good graphs of n vertices, addtionally, the first k vertices can reach each other on the outside. Now we need to consider how the first k vertices are distributed: ∀1≤u,v≤k, C(u),C(v) are not adjacent in the cycle. Where C(u) is the biconnected component that contains u. We can DP through the cycle. Note that we didn’t constrain which edge to be picked, so that every good graph is calculated for exactly deg(1) times. So we should store deg(1) in the DP state addtionally and finally divide the answer by it.
Time complexity: O(n^5),O(n^6) solutions with small constant may pass.
Credits: Kubic
This ain't 1400, it's the hardest problem of the last AGC.
E — Biconnected Graph
This problem can be solved by using the concept of Graph Theory and the properties of edge-biconnected graphs. The idea is to count the number of ways to add edges to a tree of N-1 vertices (since we have N vertices and we need to choose one vertex as the root) without creating any self-loops and ensuring that the graph remains edge-biconnected.
Here is a Python code that solves this problem:
This code calculates the number of ways to add edges to a tree of N-1 vertices without creating any self-loops and ensuring that the graph remains edge-biconnected. This is done by counting the number of ways to choose 2 edges from the remaining N-2 vertices to connect the tree with the remaining N-1 vertices.
The time complexity of this code is O(1) and the space complexity is O(1), making it efficient for solving this problem.
Too easy, do better
can you solve it attractors