Official

F - Degree Sequence in DFS Order Editorial by evima

Let us number the vertices \(1, 2, \cdots, N\) in the DFS order.

We will call a graph good when it can be traversed in the order \(1, 2, \cdots, N\) with DFS. First, in a good graph, for each \(2 \leq v \leq N\), there is an edge connecting \(v\) and some vertex \(u\) (\(u < v\)).

Here, let us call a graph goodish when, “for each \(2 \leq v \leq N\), there is an edge connecting \(v\) and some vertex \(u\) (\(u < v\))”.

For a goodish graph, we can show that there is a good graph where each vertex has the same degree as that in the goodish graph.

Proof For $a \lt b \lt c \lt d$, if the edges $(a,c)$ and $(b,d)$ exist, deleting them and adding the edges $(a,d)$ and $(b,c)$ keeps the graph goodish, without changing the degree of each vertex. If we assign the value $(u-v)^2$ to an edge $(u,v)$, the operation always increases the sum of those values, so repeating it eventually leads to a state where it cannot be applied anymore. It is easy to verify that the goodish graph obtained this way is a good graph.

Below, we will count the number of possible degree sequences of a goodish graph.

For a fixed sequence \(a=(a_1,a_2,\cdots,a_N)\) of positive integers, let us figure out the way to determine if it is a possible degree sequence.

First, it is obviously necessary that \(a_1 \leq M, \sum_{1 \leq i \leq N}a_i=2M\).

Second, let us take some \(2 \leq v \leq N\). Then, for each \(u=2,\cdots,v-1\), there has to be an edge connecting \(u\) and a vertex with an index smaller than \(u\), so there are at least \(v-2\) edges such that neither endpoint is \(v\). This observation, combined with the condition that there is no self-loop, leads to the inequalities below.

  • \(\sum_{i < v} a_i \geq 2(v-2) +1\) (\(+1\) accounts for an edge connecting Vertex \(v\) and one of the Vertices \(1,2,\cdots,v-1\))
  • \(a_v \leq M-(v-2)\)

These are necessary conditions for \(a\), but they turn out to be sufficient, too.

Proof Consider the greedy algorithm below.
  • For each $v=2,3,\cdots,N$, do the following.
  • From $1,2,\cdots,v-1$, choose a vertex $u$ to connect to $v$. Here, choose $u$ with the largest $a_u$. Decrease the values $a_u$ and $a_v$ by $1$.
If we can state that the maximum among $a_i$ is at most $M-(N-1)$ after the algorithm, we can span edges according to the remaining $a_i$. Assume that $a_i>M-(N-1)$ after the algorithm. Then, there exists $i 2M-2(N-1) = \sum_{1 \leq k \leq N} a_k$, a contradiction. This completes the proof.

By defining \(b_0=a_1\), \(b_i = a_{i+1}-1\) (\(1 \leq i \leq N-1\)), the condition that \(b\) should satisfy can be put together into the following.

  • Each \(b_i\) is non-negative integer
  • \(\sum_{0 \leq i \leq N-1} b_i=2M-(N-1)\)
  • \(\sum_{j<i} b_j \geq i\)　(\(0 \leq i \leq N-1\))
  • \(b_i \leq M-i\)　(\(0 \leq i \leq N-1\))

Let us count \(b\)s that satisfy the conditions ignoring the last one. Consider a path on grid points that starts at the origin, goes up by \(b_0\), right by \(1\), up by \(b_1\), right by \(1\), up by \(b_2\), \(\cdots\) For this path, the conditions to satisfy are not to pass the region \(y < x\) and to reach the coordinates \((N-1,2M-(N-1))\) in the end. We can count such paths in a way similar to the one involving the Catalan number.

From this count, let us try to subtract the number of paths that violate the last condition. First, for any \(b\), there is at most one \(i\) that violates the last condition.

Proof Assume that the condition is violated for $i=p,q$ ($p \lt q$). From $\sum_{j \lt p} b_j \geq p$, $b_p \geq M-p+1$, $b_q \geq M-q+1$, we have $\sum_{0 \leq i \leq N-1} b_i \geq p+(M-p+1)+(M-q+1)=2M-q+2 \gt 2M-(N-1) = \sum_{0 \leq i \leq N-1} b_i$, a contradiction, which complets the proof.

Let us fix the \(i\) that violates the last condition and name it \(K\). If we use \(b_K-(M-K+1)\) instead of \(b_K\) and consider the conditions for a path similar to the above, we will have a problem of counting paths that pass the region shown below.

picture

The shape of this region is a combination of a rectangle and a triangle. Let \((x,k)\) be the coordinates where the path touches the rectangle for the first time after starting at the bottom left. Then, we can count the paths \((0,0) \to (x,K-1)\) and the paths \((x,K) \to(N-1,M-N+K)\), so the desired paths can be counted by trying all \(0 \leq x < K\).

Finally, we will let \(K\) move and compute the sum of these values. From the fact that the number of paths \((x, K) \to(N-1, M-N+K)\) does not depend on \(K\), it is enough to find for each \(x\) the sum of the numbers of paths \((0, 0) \to (x, K-1)\) over all \(K\) such that \(x<K\). By writing the number of paths \((0, 0) \to (x, K-1)\) as a formula with combinations, we can also find the explicit formula of the sum over \(K\)s. In the end, it just takes \(O(1)\) time to compute the values required for each \(k\), for a total of \(O(N)\) time to solve the problem. Since \(M\) is not so large, spending \(O(N+M)\) time pre-computing factorials and such is acceptable.

posted:
last update: