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; }