[Codeforces Good Bye 2014 pB][Disjoint Set] New Year Permutation

原題連結
呼呼，這是並查集專題中的一題，題目本身並不難。
先對題目和並查集的聯繫做一點說明。


因為交換關係滿足傳遞性，即若i,j可互換且j,k可互換，那麼i,k也可互換。
所以可以把可交換關係想成連通分量，用並查集維護。

顯然在這張圖上每個連通分量的情況是獨立的，我們只需要分別算出最佳解答組合起來。
根據貪心思想，處理某個連通分量的方法就是直接找出字典序最小的排列(sort)，然後一個一個位置補上去即可。

這樣就成功解決了~~

#include<cstdio>
#include<algorithm>
#include<cassert>
#include<vector>
using namespace std;
const int maxn=500+5;
int fa[maxn],a[maxn];
int findset(int x) {return x==fa[x]?x:fa[x]=findset(fa[x]);}
char ch[maxn];
vector<int> pos[maxn],num[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {scanf("%d",a+i);fa[i]=i;}
    for(int i=1;i<=n;i++)
    {
        scanf("%s",ch+1);
        for(int j=i+1;j<=n;j++) if(ch[j]=='1') fa[findset(i)]=findset(j);
    }
    for(int i=1;i<=n;i++) pos[findset(i)].push_back(i),num[findset(i)].push_back(a[i]);
    for(int i=1;i<=n;i++) if(pos[i].size())
    {
        sort(pos[i].begin(),pos[i].end());
        sort(num[i].begin(),num[i].end());
        assert(pos[i].size()==num[i].size());
        for(int j=0;j<pos[i].size();j++) a[pos[i][j]]=num[i][j];
    }
    for(int i=1;i<=n;i++) printf("%d%c",a[i],i==n?'\n':' ');
}