OJ Board

I see that this is a straight forward LCS problem. Also I get the fact that as the numbers are unique we can use LIS after mapping the first sequence to the sequence 1,2.....n.

Competitive programming book (1st edition) claims that this is a straight forward LIS implementation. Is that so? So most ...

No. I mean something like Kruskal's algorithm except that we start with the given old MST and the new edges alone as the edge set to be sorted and then.....

Oh. Every time an edge threatens a cycle creation, we would again have to check the entire cycle to find out the bottleneck. But as we are ...

Thanks. Ya, I get it.I saw paths and was naively led to Dijkstra's.
And this works only because of constant edge length right? As we cover all vertices of each depth before going farther from the source, we end up with the optimal path.

Why not use Dijkistra?Though all edges are basically 1 or INF , still it should do the trick right?

Can't we add the new edges to the old MST by removing cycles as they appear?Will this greedy approach work?