ARC097 D : Equals(400)
作成日：2018.09.24
最終更新日：2018.09.24
問題概要
$1$から$N$までの整数の順列$\{p\}$に対して、操作「$j$を1つ選んで$p_{x_j}$と$p_{y_j}$を入れ替える」を任意の回数行う。
これによって$p_i = i$となる$i$の数の最大値を求めよ。
制約
$2 \leq N \leq 10^5$
$1 \leq M \leq 10^5$
$1 \leq p_i \leq N$ , $\{p\}$は順列
$1 \leq x_j,y_j \leq N$ , $x_j \neq y_j$
$j \neq k$ならば$(x_j,y_j) \neq (x_k,y_k)$
考え方
ある$i$において$p_i = i$となるように操作できる条件は、初めに$p_{r_i} = i$であったとすると$x_{a_0} = r_i$,$y_{a_k} = i$,$x_{a_t} = y_{a_{t-1}}$($1 \leq t \leq k$)($x_j$と$y_j$は適宜逆でも良い)となるような$\{a_k\}$が存在することである。
すなわち頂点$x_j,y_j$を辺で結んだ$N$頂点のグラフにおいて、$i$,$r_i$を結ぶパスがあれば良い。
これをすべての$i$について判定するには、上記のグラフにおいて頂点$i$,$r_i$が同一連結成分内にあるかを調べれば良い。
これはUnion-Findを用いれば$O(N+M)$程度(正確にはアッカーマン関数の逆数や$log$がかかる)でできる。
後はそのような条件を満たす$i$すべてにおいて、同時に$p_i = i$とできることを確認すれば良い。
これは関節点でない頂点$i$において、条件を満たすならば$p_i = i$、そうでなければ$p_k = k$とならないような$k$を1つ選んで$p_i = k$とした後に$i$を取り除くということを繰り返せば達成できる。
以上より、答えはグラフにおいて頂点$i$,$p_i$($r_i$,$i$の関係とこの順で対応していることに注意)が同一連結成分内にあるような$i$の個数であることが分かる。
ソースコード
マクロ等はこちら
Union_Find
void uni(int a , int b)
頂点$a$を含む集合と頂点$b$を含む集合を併合する
bool find(int a , int b)
頂点$a$と頂点$b$が同じ集合であるかを判定する
Union_Find uf;
int N,M;
int p[100003];
int main(){
cin >> N >> M;
repp(i,1,N+1) cin >> p[i];
repp(i,0,M){
int x,y; cin >> x >> y;
uf.uni(x,y);
}
int ans = 0;
repp(i,1,N+1) if(uf.find(i,p[i])) ++ans;
cout << ans << endl;
return 0;
}解法まとめ
頂点$x_j,y_j$を辺で結んだ$N$頂点のグラフにおいて、頂点$i$,$p_i$が同一連結成分内にあるような$i$の個数が答えである。(8-14行)