牛客615963号：#include <vector> #include <iostream> #include <string> using namespace std; int root(vector<int> &paths, int n){ int r = paths[n]; while(r != paths[r]) r = paths[r]; paths[n] = r; return r; } int main(int argc, char *argv[]) { string str; int N; while(cin >> str){ cin >> N; vector<int> paths(str.size()); for(int i=0; i<str.size(); i++) paths[i] = i; for(int i=0; i<N; i++){ int a, b; cin >> a >> b; int ra = root(paths, a); int rb = root(paths, b); if(ra < rb) paths[rb] = ra; else paths[ra] = rb; } for(int i=0; i<str.size(); i++){ for(int j=i+1; j<str.size(); j++){ if(root(paths, i) == root(paths, j)){ if(str[i] > str[j]){ char ch = str[i]; str[i] = str[j]; str[j] = ch; } } } } cout << str << endl; } return 0; } 第二题用并查集将连通的几个位置分到一组里, 然后对每个组, 做一个排序. 笔试的时候并查集有点小问题, 一直超时. 刚刚重新写了一遍竟然过了...