How to check effeciently that some changes preserve the topological ordering?


I have an acyclic directed graph with $ k$ connected components. I also have a topological ordering $ L$ (a sequence of vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering).

So, let’s say for example $ L = i_0,i_1,..,i_n$ .

I have the following operations:

  1. Exchange(i,j): it simply exchange the positions of i and j in the list. Meaning that $ L = ..,i,..,j,..$ becomes $ L’=..,j,..,i..$

  2. Inserting(i,p): it simply remove $ i$ from its position and inserts it in position $ p$ . Meaning that we have $ L=a,b,c,i,d,e,f$ then inserting(i,6) gives $ L”=a,b,c,d,e,i,f$ .

Now how to check that $ L’$ and $ L”$ are also valid topological sorting? Apart from doing a graph traversal of course because I want to exploit the two facts: i) the graph comes in $ k$ connected components and ii) some parts of $ L$ remain unchanged in $ L’$ and $ L”$ so its not useful to check them. Please consider indicating the complexity of your approaches.