Codeforces ECR #014 : D. Swaps in Permutation

ちょこちょこミスしたけど全完できたので良かった。
http://codeforces.com/contest/691/problem/D

問題

1～Nのpermutationである数列Pが与えられる。
また、２つのindexの対(a,b)が複数与えられる。

与えられたindexの対に対し、任意の順番で任意の回数Pの内容をswap出来るとき、Pを辞書順最大化せよ。

解法

swap可能な要素群をUnion-Findで連結していこう。
あとは連結成分内の要素で先頭に近い順から大きい順で配置していけば良い。

int N,M;
int P[1010101];

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<1100000> uf;
priority_queue<int> PQ[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&M);
	FOR(i,N) scanf("%d",&P[i]);
	FOR(i,M) {
		scanf("%d%d",&x,&y);
		uf(x-1,y-1);
	}
	FOR(i,N) PQ[uf[i]].push(P[i]);
	
	
	FOR(i,N) {
		x = PQ[uf[i]].top();
		PQ[uf[i]].pop();
		_P("%d%c",x,(i==N-1)?'\n':' ');
	}
}

まとめ

そういやECR011-013解ききってないなぁ…。