ARC097 D-Equals
問題概要
1 ~ Nの順列p1,p2,p3, ... ,pnが与えられる.次にm個の1 ~ Nの整数のペア(a, b)が与えられる.このペアは与えられた順列の整数aと整数b( a,b は添字のことではない )の場所をswapさせることができる. これらの操作を好きな数だけ繰り返してPi = iとなるiの数として考えうる最大値を答えよ.
解法
連結成分内なら好きなように移動することができる.つまり,移動可能な場所のグループを作ってpi と i は同じグループに属しているかを判定すれば良い.このようなグループ分けはUnion-Find木を使えば高速に処理ができるのでそれを使う.
Union-Find木はAtCoderが説明スライドを公開しているのでそちらを参照されたし.
Union-Findの説明スライド
ソースコード
class Union_Find{ private: vector<int> par, rank; int find(int x){ if(par[x] == x){ return x; }else{ return par[x] = find(par[x]); } } public: Union_Find(int Max_Node){ par.resize(Max_Node); rank.resize(Max_Node); } void init(int n) { for(int i = 0; i < n; i++){ par[i] = i; rank[i] = 0; } } void unite(int x, int y){ x = find(x); y = find(y); if(x == y)return ; if(rank[x] < rank[y]){ par[x] = y; }else{ par[y] = x; if(rank[x] == rank[y])rank[x]++; } } bool same(int x, int y){ return (find(x) == find(y)); } }; int main(){ int n, m; cin >> n >> m; vector<int> in(n); for(int i = 0; i < n; i++)cin >> in[i]; Union_Find uf(n + 10); uf.init(n + 1); for(int i = 0; i < m; i++){ int a, b; cin >> a >> b; uf.unite(a, b); uf.unite(b, a); } ll ans = 0; for(int i = 0; i < n; i++){ if(uf.same(in[i], i+1)){ ans++; } } cout << ans << endl; return 0; }
感想
考察実装込みでだいたい10分くらいで解けたので大満足. Union-Findを使う問題をあまり見たことがないのでいい練習になった.
あと,こういう記事書くの難しいよね