G? - From matcharate12

2 secs 1024 MB

matcharate12

問題

提出

テストケース

解説

この問題はグラフの考えを問います。

問題は $Q$ から $P=(1,\dots,N)$ に一致するまでにかかる入れ替える操作(以下swapといいます)の回数の最小値です。
実は次のグラフを構成することが可能です。

$i=1,2,\dots,N$ において $Q_i\ne P_i$ であるとき、頂点 $Q_i$ から頂点 $P_i$ に無向辺を張る

このグラフにおいて、どの $1$ つの頂点に注目しようと次数が $1$ であることが証明できます。
( $P,Q$ ともに順列の定義からすべて異なる要素からなるといった性質より容易に示すことが可能なので、ここでは省略します)

そうしてできるグラフは、各連結成分ごとに連結なグラフであるため、互換いわゆる異なる $2$ 要素のswapの操作に等しくなることが分かります。
したがって頂点 $v$ から頂点 $u$ に無向辺がつながるということは、順列 $P$ でいう $2$ 要素 $v,u$ を入れ替えることに相当します。

これを繰り返していくと、やがて操作が一周してきます(すなわち一度行ったswapが再び行われる)。
操作が一周するのにかかるswapの回数は、各連結成分が構成される辺の本数から $1$ 引いたものに一致します。
ここで構成されるグラフは必ずしも連結、すなわち連結成分の個数が $1$ とは限らないことに注意してください(制約から明らかに $Q_k\ne P_k$ がすべての $k$ で成り立つとは限らない)。

以上から各連結成分 $C_j\ (1\le j\le n)$ 、 $C_j$ が構成される辺の数を $|C_j|$ 、連結成分の個数 $n$ とおくと、答えは $\displaystyle\sum^{n}_{k=1}(|C_k|-1)$ となります。

連結成分に属する頂点の個数の列挙は UnionFind や DFS などのグラフ探索アルゴリズムを用いて $O(N)$ で実装が可能であることから、全体で $1$ ケースあたり $O(N)$ で実装することができます。
よってこの問題を正解することができました。

※ちなみに伝えたかったことは

「人生の計画の順番を正しく変えるのにこんだけ時間がかかるんだから、計画したことは変えてはいけない。泥をかけられてもやり通せ」

です(すげぇ無理やり感)。

この解答例は、宝刀「UnionFind」を用いて実装しています。

xxxxxxxxxx
 
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++) //[0,n)
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
​
struct UnionFind {
    vector<int> par,rank,siz;
    UnionFind(int n):par(n,-1),rank(n,0),siz(n,1) {}
​
    int root(int x){
        if(par[x] == -1) return x;
        return par[x] = root(par[x]);
    }
​
    bool same(int x,int y){
        int rx = root(x),ry = root(y);
        return rx == ry;
    }
​
    bool unite(int x,int y){
        int rx = root(x),ry = root(y);
        if(rx == ry) return 0;
​
        //union by rank
        if(rank[rx] < rank[ry]) swap(rx,ry);
        par[ry] = rx;
        if(rank[ry] == rank[rx]) rank[rx]++;
        siz[rx] += siz[ry];
        return 1;
    }
​
    int size(int x){ return siz[root(x)]; }
};
​
int main(){
    int T; cin >> T;
    while(T--){
        ll N,K; cin >> N >> K;
        vector<int> Q(N); rep(i,N) cin >> Q[i];
​
        UnionFind uf(N);
        int t = 0,t2 = 0;
        rep(i,N) if(Q[i] != i+1) uf.unite(Q[i]-1,i);
​
        vector<int> cnt(N,0);
        rep(i,N) cnt[uf.root(i)]++;
​
        int ans = 0;
        rep(i,N) if(cnt[i] > 0) ans += cnt[i]-1;
        cout << (ans <= K ? "Yes" : "No") << endl;
    }
}
​