DFS Start/Finish Time¶
In this section, we want to convert a graph into an array using a trick.
There are various ideas to convert a graph into an array, and starting time is one of them. Using this idea, the given graph can be transformed into an array, making it easier to solve various types of problems.
For each vertex, we can consider the first time the DFS algorithm enters it. In this way, each vertex has a unique number, and the vertices can be sorted according to these times to form an array.
Suppose the array we want to create from the graph's vertices is a[i], and the time when the DFS algorithm enters vertex u is st[u]. In this case, we place vertex u at index st[u], or in other words, a[st[u]] = u.
It is clear that each subtree of its DFS tree corresponds to an interval in the array.
Finishing time is defined similarly to starting time, with the difference that it indicates the time when the DFS algorithm exits a vertex.
Now, let's examine a few problems.
Checking Ancestor/Descendant Relationship in Linear Time¶
We are given an \(n\)-vertex tree along with \(q\) queries. In each query, we need to check whether vertex \(u\) is an ancestor of vertex \(v\). \(O(n+q)\)
Solution¶
We use the lemma that the necessary and sufficient condition for an ancestor-descendant relationship is as follows: \(stt[u] \le stt[v]\) and \(fnt[v] \le fnt[u]\) or \(stt[u] \le stt[v]\) and \(stt[v] < fnt[u]\)
The correctness of this lemma can be easily verified. So, to solve the problem, we first perform a DFS on the tree, and then for each query, we check the given condition in \(O(1)\) time.
Finding the k-th Parent¶
We are given an \(n\)-vertex tree along with \(q\) queries. In each query, we need to find the \(k\)-th parent of vertex \(v\). \(O(n+q \cdot \log(n))\)
Solution¶
Consider all vertices with height \(h[v]-k\). Using the lemma from the previous problem, we can conclude that the answer is the vertex with the maximum starting time less than the starting time of vertex \(v\) among vertices at height \(k\) levels higher. In other words,
u with maximum stt such that h[u] = h[v] - k and stt[u] <= stt[v]
For each height, create a vector of all vertices at that height, where the vertices in each vector are sorted by their starting times. \(O(n)\)
Now, each query transforms into a binary search on one of these vectors!
Blood Cousins¶
An \(n\)-vertex tree with \(m\) queries of the form v p is given. For each query, you need to output the number of \(u\)'s such that the p-th parent of v and u are the same. \(O(n+q \log(n))\)
Solution¶
First, find the p-th parent of vertex v similar to the previous problem. Let's call this vertex w. Now, the answer is the number of u's such that \(h[u] = h[v]\), \(stt[w] \le stt[u]\), and \(stt[u] < fnt[w]\). This means we want the count of starting times within a specific range in the vector corresponding to vertex v, which can be solved with a simple binary search.
Biconnecting with Minimum Number of Paths¶
Given an \(n\)-vertex tree with \(2k\) leaves. In each operation, we can choose two leaves and color all edges on the path between them. Find the minimum number of operations required and a method with the minimum number of operations to color all edges. \(O(n)\)
Solution¶
Answer = k Next, we will present a method and demonstrate its correctness. If n=2, the problem is trivially solved. So assume n > 2 and we have at least one non-leaf vertex. Root the tree at a non-leaf vertex and number the leaves according to their starting times. Now perform operations on these leaf pairs:
Clearly, the complexity of this pairing is \(O(n)\).
Now we must show that all edges are colored. The subtree of each edge covers an interval of leaves. For an edge to be colored, we must have a pair of leaves where one end is inside this interval and the other end is outside of it. Assume the interval for the edge in question is \([l, r]\). We consider two cases. First, if \(l \le k\) and \((k+1) \le r\). In this case, if \(l \ne 1\), the pair (1, k+1) falls within the interval. Otherwise, the pair (k, 2k).
If the interval corresponding to the edge is not similar to the previous case, without loss of generality, we assume \(l, r \le k\). In this case, the pair (r, r+k) also colors this edge.
Therefore, in both cases, the desired edge is colored, and the pairs we formed are valid.
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at اکتبر 13, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
