まず、任意の木から上の手順で構成した順列は \(i \rightarrow P(i)\) に辺を貼ったときにサイクルが一つになることに注目します。(これは上のグラフで非連結な成分同士を swap すると連結されることから示すことができます。)

サイクルを有向辺の向きが時計周りになるように環状に並べます。処理を逆順に考えたとき、ある辺を選ぶことは、その辺を時計回りに少しずらした直線でサイクルを分断していることと対応しています。

分断された頂点集合を結ぶような辺があった場合、この後どのように操作を行っても元の順列に戻すことは不可能です。

実は、サイクル内で端点以外に交差を持たないように辺を木になるように書き入れることが出来れば、順番をうまく選ぶことで与えられた順列にすることができます。上の考察をもとに、処理を逆向きに見てみます。

頂点 \(x\) から複数の辺が出ているとします。このとき、処理する順番は逆側の端点が \(x\) から見て時計周りに動いて見つかった順に処理する必要があることがわかります。逆に、この順序付けがトポロジカルソート可能ならば求める順列を得ることができます。(辺が交差していないことから、上記のルールで決められた順序が守られているとき、どの直線も自分が処理される前に分断されることはあり得ません。)、これは木であることから明らかに順序付け出来ることがわかります。(辺を順番に辿ると、DFS と同じ要領で同じ辺に戻ることはない。)

よって、サイクルが \(1\) つにならない場合や与えられた辺同士が交差するなら解は存在せず、そうでない場合は必ず構成が可能です。(例えば、サイクルの外側の辺を必要な部分だけ結べば良いです。)

計算量は \(O(N \log N)\) 等です。