ABC233F Swap and Sort - geam1113’s diary

解説AC。大体の解法は自分が想定したものと合っていました。

ここでは、 $P_i$ を、頂点iに書かれた整数と表現します。

「i番目とj番目が交換可能」という条件を「頂点iと頂点jに無向辺がある」と言い換えます。

昇順に並び替えるとは、

すべての頂点 $i$ について、 $i$ と $P_i$ が等しい

と同値です。上記を達成するためには、

すべての連結成分について、同一な連結成分に属する頂点番号の集合 $V_i=\{v_j,v_{j+1},...\}$ とその頂点に番号に書かれた $P$ の集合 $Q_i=\{P_{v_j},P_{v_{j+1}},... \}$ が一致する。

となります。
一見ややこしいですが、すべての $P_i$ について辺を辿って $i=P_i$ となる位置に移動できるということを示しています。

次に、操作回数Kの制約があるため、操作回数のワーストを考えます。
頂点が5個の時を例にすれば、

V -> 1-2-3-4-5
P -> 5-4-3-2-1

上記のように頂点が昇順に連結し、Pが降順となっていた時が、バブルソートの交換回数と同様にワーストになると予想できます。
この時、交換回数は
$4+3+2+1=\frac{5(5-1)}{2}$
です。よって、N=1000の時、 $\frac{1000(1000-1)}{2}=499,500\lt 500,000$
となり、Kの制約に適合します。従って、 $V_i=Q_i$ さえ保たれていれば、グラフはどのような形をしていても達成可能だということがわかります。

ここで、各頂点からDFSし、頂点iに本来納まるべき整数を順次持ってくる解法が思いつきます。しかし、各頂点からDFSした場合の計算量は $O(N(N+M))$ となり間に合いません。

前述したように、グラフの構造は何でも良いので、全域森にしてしまえばよいです。全域森はKruskul法で構築できます。よって、辺の数は最大でも $N-1$ 個となり、計算量が間に合います。

今回、頂点と整数は葉である頂点から順に一致させていく必要があります。この実装でかなりつまづきました。
最終的な実装としては、

次数1以下の点をキューに追加する
キューが空になるまで以下を繰り返す
1. キューから頂点を1つ取り出しuとする。
2. uからDFSして整数を一致させる。この時辿った辺を操作列に追加する。もし一致できなかったら-1を出力して終了。
3. uを決定済みとする。
4. u及びuと隣接するすべての頂点 $v_i$ の次数を1減らす。 $v_i$ の次数が1以下でかつ未決定ならキューに追加する。

という風にしました。最初に葉をキューに追加する時は、次数0も追加しないといけません。なぜなら、

V -> 1-2 3 4
Q -> 2-1 4 3

というケースなどでWAとなります。
別に実装してみましたが、次数を減らした後に頂点 $v_i$ を追加する時の条件は、「 $v_i$ の次数が1である」のみにしてもよく、整数が決定済みかどうかという条件は省けました。

DFSでは、始点sと頂点uに書かれた整数が等しい場合に、始点sまで順次交換操作を行い、辺番号を操作列に追加します。

bool dfs(int s, int u, int p=-1) { //sは始点である頂点番号、uは現在訪問している頂点番号、pは親の頂点番号
    if (P[u]==s) return true; // 始点である頂点sと現在訪問している頂点uに書かれたP[u]が一致したら、trueを返す。
    for (auto&& e : g[u]) { //辺を示す構造体{始点from,終点to,番号id,コストcost}
        int v = e.to; //頂点uの辺eに接続する頂点v
        int id = e.id; //辺の番号。今回は操作番号に一致。
        if (v==p) continue; //親なら無視。木を前提としているため。
        if (dfs(s,v,u)) {  //始点sと一致する整数が見つかったら、
            swap(P[u],P[v]); //書かれた整数を交換する
            ans.pb(id); //操作列に辺番号を追加
            return true;
        }
    }
    return false;
}

提出コード