3
$\begingroup$

I'm practicing for ACM ICPC and I came on this problem from 2017 ACM ICPC Arab Regionals:

First, let’s define an undirected connected labeled graph, it’s a graph with N nodes with a unique label for each node and some edges, there’s no specific direction for each edge, also duplicate edges and edges from a node to itself aren’t allowed, and from any node you can reach any other node. A bridge in such graph is an edge that if we remove it, the graph will be disconnected (there will exist nodes which aren’t reachable from each other). In this problem you are given N and K, and your task is to count the number of different undirected connected labeled graphs with exactly N nodes and K bridges. Since that number can be huge, print it modulo M. An edge is defined using the labels of the nodes it connects, for example we can say (X, Y ) is an edge between X and Y , also (Y,X) is considered the same edge (since it’s undirected). Two graphs are considered different, if there’s an edge which exists in one of them but not the other.

Input:

Your program will be tested on one or more test cases. The first line of the input will be a single integer T (1 ≤ T ≤ 100) representing the number of test cases. Followed by T test cases. Each test case will be just one line containing 3 integers separated by a space, N (1 ≤ N ≤ 50), K (0 ≤ K < N) and M (1 ≤ M ≤ 10^9), which are the numbers described in the statement. It’s guaranteed that N will not be more than 25 in 95% of the test cases

Output:

For each test case, print a single line with the number of graphs as described above modulo M.

Sample Input:
4
3 2 10
3 0 10
6 3 10000 
6 3 1000

Sample Output
3
1
2160
160

I tried to come up with some formula that would work for all N and K but I had no success. I already asked this on Stack Overflow but nobody answered. Can someone tell me what should I do to solve it, because I couldn't find any editorial? Thanks in advance

$\endgroup$
  • 1
    $\begingroup$ Why do you believe there is such a formula? $\endgroup$ – Alex Vong May 13 '18 at 17:01
  • 1
    $\begingroup$ Same question here: stackoverflow.com/questions/50309296/… $\endgroup$ – Szabolcs May 14 '18 at 14:59
  • $\begingroup$ Possibly helpful Other than that. An exact formula probably doesn't exist, but an algorithm or a recurrence relation probably exists. $\endgroup$ – kingW3 May 26 '18 at 12:35
1
+200
$\begingroup$

Choose an ordered pair of nodes to be a bridge, in $N(N-1)$ ways. If this bridge were removed, the graph would be divided into the "left half" and the "right half", each of which must still be a connected component. So, partition the remaining $N-2$ nodes between the left and right halves of the bridge; there are ${{N-2}\choose{m}}$ ways to assign $m$ nodes to the left half and $N-m-2$ to the right half, and we need to sum over $m$. Also partition the remaining $K-1$ bridges between the left half and the right half of the bridge: assign $k$ to the left half and $K-k-1$ to the right half, where we sum over $k$. You now have two independent pieces: the left half, with $N_L=m+1$ nodes and $K_L=k$ bridges, and the right half, with $N_R=N-m-1$ nodes and $K_R=K-k-1$ bridges. Note that $N_L,N_R < N$ and $K_L,K_R < K$, so we can calculate this recursively. Specifically, if $A_{N,K}$ is the number of undirected, labeled, connected graphs with $N$ nodes and $K$ bridges, then $$ A_{N,K}=\frac{N(N-1)}{2K}\sum_{m=0}^{N-2}\sum_{k=0}^{K-1}{{N-2}\choose{m}}\cdot A_{m+1,k}\cdot A_{N-m-1,K-k-1}. $$ (The factor of $2K$ is needed because we are counting each graph $2K$ times, due to the $K$ possible bridges to consider first and the $2$ possible orientations of that bridge.) Obvious boundary conditions are that $A_{1,0}=1$ and $A_{1,K}=0$ for $K>0$. Unfortunately we still don't know $A_{N,0}$, the number of bridgeless connected graphs on $N$ nodes... we need to calculate that separately. The only way I came up with to do this was to calculate the total number of connected graphs, then subtract off the number with exactly $K$ bridges for each $K\ge 1$: $$A_{N,0}=C_{N} - \sum_{K=1}^{N-1}A_{N,K}.$$ This seems inelegant, and I welcome an alternate approach that counts bridgeless graphs directly... but failing that...

Let's count all the connected graphs on $n$ nodes. We can choose any node in the graph and work outward from it, letting the number of nodes at distance $i\ge 1$ be $m_i$; each node at distance $i$ must have at least one edge to a node at distance $i-1$, giving $(2^{m_{i-1}}-1)^{m_i}$ choices; and any set of edges among the nodes at distance $i$ is allowed, giving an additional factor of $2^{m_i(m_i-1)/2}$. Finally, the number of ways to assign nodes to levels is $\frac{(n-1)!}{m_1!m_2!\ldots}$. Hence $$ C_{n}=(n-1)!\sum_{M} \prod_{i=1}^{\ldots} \frac{(2^{m_{i-1}}-1)^{m_i} 2^{m_i(m_i-1)/2}}{m_i!}=(n-1)!\sum_{M} \prod_{i=1}^{\ldots} \frac{\left(2^{(m_i-1)/2}(2^{m_{i-1}}-1)\right)^{m_i}}{m_i!}, $$ where $m_0=1$ and the sum is over all positive sequences $(m_1,m_2,\ldots)$ such that $1+\sum_i m_i = n$. To write this more manageably as a recursion, let $D_{k,m}$ be the number of ways to arrange $m$ additional nodes after a layer of $k$ with these same constraints (that each node connects to at least one in the previous layer, and any set of connections within the same layer is allowed). Then $$ D_{k,m}=\sum_{l=1}^{m}{{m}\choose{l}}(2^k-1)^l2^{l(l-1)/2}D_{l,m-l}, $$ in terms of which $C_n=D_{1,n-1}$. Putting everything together, the following code calculates the number of connected graphs on $N$ labeled nodes with exactly $K$ bridges (leaving out the obvious memoization, which is required to make it efficient, but hurts readability):

def D(k, m):
  return sum([binom(m, l) * (2**k - 1)**l * 2**(l*(l-1)/2) * D(l, m-l) for l in xrange(1, m+1)])

def C(n):
  if n<=1: return 1
  return D(1, n-1)

def A(N, K):
  if N<=1:
    if K==0: return 1
    return 0
  if K==0:
    return C(N) - sum([A(N, k) for k in xrange(1, N)])
  ret = 0
  for m in xrange(N-1):
    for k in xrange(K):
      ret += binom(N-2, m) * A(m+1, k) * A(N-m-1, K-k-1)
  return ret * N * (N-1) / (2 * K)

And the first few results are the following (in the format $N, K, A(N,K)$):

1 0 1
2 0 0
2 1 1
3 0 1
3 1 0
3 2 3
4 0 10
4 1 12
4 2 0
4 3 16
5 0 253
5 1 200
5 2 150
5 3 0
5 4 125
6 0 11968
6 1 7680
6 2 3600
6 3 2160
6 4 0
6 5 1296
7 0 1047613
7 1 506856
7 2 190365
7 3 68600
7 4 36015
7 5 0
7 6 16807
8 0 169181040
8 1 58934848
8 2 16353792
...
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.