CFR 500 B. New Year Permutation ( Greedy + Union Find )

Problem - 500B - Codeforces
如果某兩個數可以交換，那麼可以和那兩個數的任意一個交換的數同樣能和另一個交換，所以我們可以維護一個集合代表當前的位子可以用的數字有哪些。欲處理完就能貪心的由左到右依次選取集合中最小的。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300 + 3;

char G[ MAXN ][ MAXN ];
int n;
int a[ MAXN ];
int pos[ MAXN ];

struct UnionFind{
    int fa[ MAXN ];
    void init(int z){
        for(int i = 1; i <= z; ++i)
            fa[ i ] = i;
    }
    int find(int x){ return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] ); }
    bool unite(int x, int y){
        int a = find( x );
        int b = find( y );
        if( a == b ) return false;
        fa[ a ] = b; return true;
    }
} uf;

set<int> st[ MAXN ];
int ans[ MAXN ];

void solve(){
    for(int i = 1; i <= n; ++i)
        st[ uf.find( i ) ].insert( a[ i ] );
    for(int i = 1; i <= n; ++i){
        ans[ i ] = *st[ uf.find( i ) ].begin();
        st[ uf.find( i ) ].erase( st[ uf.find( i ) ].begin() );
    }
    for(int i = 1; i <= n; ++i)
        printf("%d%c", ans[ i ], i == n ? '\n' : ' ');
}

int main(){
    scanf("%d", &n);
    uf.init( n );
    for(int i = 1; i <= n; ++i){
        scanf("%d", &a[ i ]);
        pos[ a[ i ] ] = i;
    }
    for(int i = 1; i <= n; ++i){
        scanf("%s", G[ i ] + 1);
        for(int j = 1; j <= n; ++j) if( G[ i ][ j ] == '1' )
            uf.unite( i, j ); // has_edge
    }
    solve();
    return 0;
}