题目链接：http://www.spoj.com/problems/LEXSTR/

题意是给一个字符串str，然后给出m个数对 i , j； 代表str[i] 和 str[j] 可以互相之间交换任意次 ，然后问如何交换使得这个字符串的字典序最小，输出这个字典序最小的字符串。

字符串长度是1e5.

一开始我这样想：如给两个数对（i，j）、（i，k），那么j和k也是可以交换的，但是稍微看一下就知道复杂度是不够的，后来再看一下发现，其实把i、j、k都拿出来并按字典序排一下序就可以了。也就是说对于一个数对（i，j）中的 i ，跟i有直接或者间接关系的，都可以直接拿出来按字典序排个序。

找直接关系间接关系这里很耳熟啊，是啊，用并查集就可以完成了；

对这些数对做一些并查集，然后可以分成几个部分，对每个部分我们按照字典序对字符串排序，就好了；

#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<set>
#include<map>
#include<time.h>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<iostream>
using namespace std;
#define  LONG long long
const int   INF=0x3f3f3f3f;
const int MOD=1e9+7;
const double PI=acos(-1.0);
#define clrI(x) memset(x,-1,sizeof(x))
#define clr0(x) memset(x,0,sizeof x)
#define clr1(x) memset(x,INF,sizeof x)
#define clr2(x) memset(x,-INF,sizeof x)
#define EPS 1e-10
int num[100100][2];
char str[100100];
int f[100100];
int findset(int x )
{if(f[x] == x)return x;else return f[x] = findset(f[x]);
}
char tmp [100100];
int tmpp[100100];
int main()
{int T;cin>>T;while(T--){scanf("%s",str);int len = strlen(str);int m ;cin>>m;for(int i = 0; i <= len +10; ++ i)f[i] = i;for(int i = 1; i<=m ; ++ i){int q , p;scanf("%d%d",&p,&q);if(p > q) swap(q , p);int r1 = findset(p) ;int r2 = findset(q) ;f[r1] = r2;f[p] = r2;f[q] = r2 ;}for(int i = 0 ; i <len ;++ i)f[i] = findset(i) ;vector <int > vec[len + 3];for(int i = 0 ; i < len ; ++ i) vec[i].clear();for(int i = 0 ; i < len ;++ i){vec[f[i]].push_back(i);}for(int i = 0 ; i< len ;++ i){int k = 0;for(int j = 0 ; j <vec[i].size() ; ++ j ){int t = vec[i][j];tmp[++k] = str[t];tmpp[k] = t;}sort(tmp + 1 , tmp +k + 1 );sort(tmpp + 1 ,tmpp + k + 1);for(int j = 1 ; j <= k ; ++ j)str[tmpp[j]] = tmp[j];}for(int i = 0 ; i < len ; ++ i) vec[i].clear();printf("%s\n",str);}
}