题目链接：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); } }