Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

### tehqin's blog

By tehqin, history, 2 years ago, ,

• +54

 » 2 years ago, # |   +6 Hello, firstly thanks for the awesome episode. I had a query. Can you tell me if the following is correct which I've understood from this episode ? Dominator tree can be constructed using LCA. To do that, we first topologically sort the nodes in the DAG. Then we process them sequentially. While processing a node, we find out the LCA of the set of nodes who have a direct edge to the current node. Then we can safely say that this LCA is the immediate dominator of the current node. So we simply add the current node as a child of the LCA we've found in the dominator tree and add the sparse table row for the current node in O(logn). Thus we can construct the whole tree. I think the time complexity would be O(ElogV) as we are finding out LCA once for every edge.Are the idea I described above and the time complexity analysis correct ?
•  » » 2 years ago, # ^ |   +5 Yes! :)
•  » » » 2 years ago, # ^ |   +5 Thanks. Also is there any other way to build a dominator tree which is more efficient ? I've seen that some people use another method involving DSU but it seemed pretty complicated at first glance.
•  » » » » 2 years ago, # ^ |   +5 Yes. That algorithm works even for graphs with cycles. It is close to linear in runtime. The LCA method only works for DAGs but is much simpler conceptually. It's only a bit slower but the binary lifting table on the dominator tree is sometimes useful for solving other subproblems.I will do a future episode on the more power algorithm if there is interest. :)
•  » » » » » 2 years ago, # ^ |   0 That would be really great. :D