Swaps in Permutation [Codeforces 教育 14 : D]

問題

http://codeforces.com/contest/691/problem/D

n 個の順列と m 個のペアが与えられる。
与えられたペアの要素間でしか、入れ替えができないとする。
このとき入れ替えてできる、辞書順最大の順列を答えよ。

1 <= n,m <= 10^6

考察

1. 例で考えて、実験してみる

9 6
1 2 3 4 5 6 7 8 9
1 4
4 7
2 5
5 8
3 6
6 9
|<<
2. 要素1と要素4で交換可能、要素4と要素7で交換可能 -> 要素1,4,7間は自由に配置を変えられる
3. バブルソート的なことをやればできる
4. 交換可能をグラフ間の連結として考えると、<b>連結な頂点間の数は自由に再配置可能である</b>ということが言える
5. これが分かれば、あとは連結成分を取り出して、連結成分内を降順ソートすれば答え

6. 連結成分の抽出は、UnionFindとmapでやりましたが、もっといい方法がありそう -> connected()

** 実装
[http://codeforces.com/contest/691/submission/19093427]
>|cpp|
template<int um> class UF { // from kmjp
public:
	vector<int> par;
	UF() { par = vector<int>(um, 0); rep(i, 0, um) par[i] = i; }
	int operator[](int x) { return par[x] == x ? x : par[x] = operator[](par[x]); }
	void operator()(int x, int y)
	{
		x = operator[](x); y = operator[](y);
		if (x != y) par[x] = y;
	}
};
//-----------------------------------------------------------------
int n, m;
int p[1010101];
int a[1010101], b[1010101];
//-----------------------------------------------------------------
map<int, vector<int> > connected() {
	UF<1010101> uf;
	rep(i, 0, m) uf(a[i], b[i]);

	map<int, vector<int> > con;
	rep(i, 0, n) con[uf[i]].push_back(i);
	return con;
}
//-----------------------------------------------------------------
int main() {
	scanf("%d %d", &n, &m);
	rep(i, 0, n) scanf("%d", &p[i]);
	rep(i, 0, m) scanf("%d %d", &a[i], &b[i]), a[i]--, b[i]--;

	auto con = connected();

	for (auto pa : con) {
		vector<int> vec;
		for (int i : pa.second) vec.push_back(p[i]);
		sort(vec.begin(), vec.end(), greater<int>());
		rep(i, 0, pa.second.size()) p[pa.second[i]] = vec[i];
	}

	rep(i, 0, n) printf("%d ", p[i]);
	printf("\n");
}