CFR Educational 14 D. Swaps in Permutation ( Union Find )

http://codeforces.com/contest/691/problem/D
Being able to swap as many times, that means swappable positions are in the same disjoint set, where in each disjoint set values in those positions could be arranged arbitrarily. We have to manage the sets with union find, and have smaller positions get higher values from each set. I made quite a mess with std::map, and probably using priority_queue will be enough and more concise.

struct UnionFind{
    vi par;
    set< int > head;
    map< int, vi > members;
    UnionFind( int _sz ){
        par.resize( _sz + 1 );
        for( int i = 1; i <= _sz; ++i )
            par[ i ] = i;
    }
    int find( int x ){
        return par[ x ] == x ? x : par[ x ] = find( par[ x ] );
    }
    bool unite( int x, int y ){
        int a = find( x );
        int b = find( y );
        if( a == b ) return false;
        par[ a ] = b; return true;
    }
};

void solve(){
    int N, M; cin >> N >> M;

    vi A( N + 1 );
    for( int i = 1; i <= N; ++i )
        cin >> A[ i ];

    UnionFind uf = UnionFind( N );
    for( int i = 0; i < M; ++i ){
        int u, v; cin >> u >> v;
        uf.unite( u, v );
    }

    vi pos( N + 1 );
    for( int i = 1; i <= N; ++i )
        pos[ A[ i ] ] = i;

    vi ans( N + 1 );
    map< int, vi > head2val;
    map< int, vi > head2pos;
    for( int i = N; i >= 1; --i )
        head2val[ uf.find( pos[ i ] ) ].push_back( i );
    for( int i = 1; i <= N; ++i )
        head2pos[ uf.find( i ) ].push_back( i );

    for( auto h : head2val ){
        int sz = head2val[ h.first ].size();
        for( int i = 0; i < sz; ++i )
            ans[ head2pos[ h.first ][ i ] ] = head2val[ h.first ][ i ];
    }

    for( int i = 1; i <= N; ++i )
        cout << ans[ i ] << ( i == N ? '\n' : ' ' );
}