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行)

ARC097の他の問題 C E F

広告

自己紹介

赤になりたい競技プログラマー/バランス重視
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告