题目链接：http://codeforces.com/problemset/problem/500/B
题目意思：给出一个含有 n 个数的排列：p1, p2, ..., pn-1, pn。紧接着是一个 n * n 的矩阵A，当且仅当 Aij = 1 时，pi 与 pj 可以交换数值。现在问如何交换数值，使得最后得到的排列字典序最小。
比赛的时候不会做，看了Tutorial 1 的解法，觉得别人做得太巧妙了，出题者也出得很好 ^_^
可以看这个：http://codeforces.com/blog/entry/15488
它是利用了并查集来做的。如果遇到 Aij = 1 的话，就将点 i 和 点 j 连一条边。最终会得到一些互不相交的集合。以第一组 test 来说吧～～～
这就表示位置 1、4、7 的数是可以交换的，位置 2、5 要保持原封不动，位置 3、6 的数可以交换。由于每个集合都有一个祖先，即第一层的那个数，依次为 7、2、5、6，然后就把每个集合的数放到以该集合祖先为首的 vector 数组里面，并把每个集合内的数从小到大排序。最后遍历位置 1 ～ n，根据每个位置的数所属的集合（以哪个祖先为首），依次输出。
只能说，解题思路真是太巧妙兼神奇！竟然可以转化成图！继续干爸爹吧 ^_^
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std; const int maxn = + ;
int p[maxn], cnt[maxn];
int group[maxn];
char s[maxn];
vector<int> vi[maxn]; int find(int x)
{
if (x == group[x])
return x;
return group[x] = find(group[x]);
} void merge(int x, int y)
{
int fx = find(x);
int fy = find(y);
if (fx != fy)
group[fx] = fy;
} int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE
int n;
while (scanf("%d", &n) != EOF)
{
vi[n].clear();
for (int i = ; i <= n; i++) {
scanf("%d", &p[i]);
group[i] = i;
}
for (int i = ; i <= n; i++) {
scanf("%s", s+);
for (int j = ; j <= n; j++) {
if (s[j] == '') {
merge(i, j);
}
}
}
for (int i = ; i <= n; i++) {
vi[find(i)].push_back(p[i]); // 千万不要写成 vi[group[i]].push_back(p[i]);
}
for (int i = ; i <= n; i++) {
sort(vi[i].begin(), vi[i].end());
}
memset(cnt, , sizeof(cnt));
for (int i = ; i <= n; i++) {
int g = group[i];
printf("%d%c", vi[g][cnt[g]++], i == n ? '\n' : ' ');
}
}
return ;
}
注意，代码中的 51 行的部分，如果写成 vi[group[i]].push_back(p[i]) 是错的！以第二个 test 为例，group[1] = 3，find[1] = 5。find[i] 才会找到最终的祖先！！！