困兽之斗

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int find(vector<int> &, int);
void merge(vector<int> &, int, int);

int main() {
	string s;
	while (cin >> s) {
		int len = s.length();
		vector<int> indexs(len, -1);
		int cnt;
		cin >> cnt;
		for (int i = 0; i < cnt; ++i) {
			int from, to;
			cin >> from >> to;
			int froot = find(indexs, from);
			int troot = find(indexs, to);
			if (froot != troot) {
				merge(indexs, froot, troot);
			}
		}
		vector<vector<int>> mat(len);
		for (int i = 0; i < indexs.size(); ++i) {
			if (indexs[i] == -1) continue;
			int root = find(indexs, i);
			mat[root].push_back(i);
		}
		for (int i = 0; i < mat.size(); ++i) {
			vector<char> chs;
			for (int j = 0; j < mat[i].size(); ++j) {
				chs.push_back(s[mat[i][j]]);
			}
			sort(chs.begin(), chs.end());
			for (int j = 0; j < mat[i].size(); ++j) {
				s[mat[i][j]] = chs[j];
			}
		}
		cout << s << endl;
	}
	return 0;
}

int find(vector<int> &indexs, int i) {
	int ret = i;
	while (indexs[ret] >= 0) {
		ret = indexs[ret];
	}
	int q;
	for (int p = i; p != ret; p = q) {
		q = indexs[p];
		indexs[p] = ret;
	}
	return ret;
}

void merge(vector<int> &indexs, int i, int j) {
	int t;
	if (indexs[i] < indexs[j]) {
		indexs[i] += indexs[j];
		indexs[j] = i;
	} else {
		indexs[j] += indexs[i];
		indexs[i] = j;
	}
}

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

int dsu[10001]={0};

int find(int x)
{
    int r=x;
    while(dsu[r]!=r)
        r=dsu[r];
    dsu[x]=r;
    return r;
}

void join(int x, int y)
{
    int fx=find(x);
    int fy=find(y);
    if(fx<fy)
        dsu[fy]=fx;
    else
        dsu[fx]=fy;
}

int main()
{
    string s;
    while(cin>>s)
    {
        int n;
        cin>>n;
        int len = s.size();
        for( int i=0; i<len; ++i)
            dsu[i]=i;
        while(n--)
        {
            int a,b;
            cin>>a>>b;
            join(a,b);
        }
        for(int i=0; i<len-1; ++i)
            for(int j=i+1; j<len; ++j)
            {
                int fj=find(i);
                int fj1=find(j);
                if(fj==fj1 && s[i] > s[j])
                    swap(s[i],s[j]);
            }
        cout<<s<<endl;
    }
    return 0;
}

// ***，通过了所有用例
//算法的思路：用一下例子说明
//dcba
//2
//0 1
//3 2
//s="dcba";
//vector<int> p初始为{0000}
//根据
//2
//0 1
//3 2
//将p设置为{1122}
//也就是s的下标0 1对于1，s的下标3 2对应2
//就是说把s中连成串的可以相互交换的字符的下标对应为同一个数字
//算了，玛德不知道怎么表达了，反正想看的自己看吧，主体思想在上面。
//#include "stdafx.h"
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

bool cmp(char it1, char it2)
{
	return it1 < it2;
}

void getStr(string s, vector<vector<int>> arr)
{
	vector<int> p(s.size(), 0);
	int i = 0;
	int color = 1;
	for (; i < arr.size(); i++)
	{
		if (p[arr[i][0]] == 0 && p[arr[i][1]] == 0)
		{
			p[arr[i][0]] = color;
			p[arr[i][1]] = color;
			color++;
		}
		if (p[arr[i][0]] == 0 && p[arr[i][1]] != 0)
		{
			p[arr[i][0]] = p[arr[i][1]];
		}
		if (p[arr[i][0]] != 0 && p[arr[i][1]] == 0)
		{
			p[arr[i][1]] = p[arr[i][0]];
		}
		if (p[arr[i][0]] != 0 && p[arr[i][1]] != 0 && p[arr[i][0]] != p[arr[i][1]])
		{
			int tmpColor = p[arr[i][1]];
			for (int j = 0; j < s.size(); j++)
			{
				if (p[j] == tmpColor)
				{
					p[j] = p[arr[i][0]];
				}
			}
		}
	}
	int color2 = 1;
	while (color2 <= color)
	{
		vector<int> index;//保存字符的下标
		vector<char> sTmp;
		for (int j = 0; j < s.size(); j++)
		{
			if (p[j] == color2)
			{
				index.push_back(j);
				sTmp.push_back(s[j]);
			}
		}
		sort(sTmp.begin(), sTmp.end(), cmp);
		for (int j = 0; j < index.size(); j++)
		{
			s[index[j]] = sTmp[j];
		}
		sTmp.clear();
		index.clear();
		color2++;
	}
	cout << s << endl;
}


int main()
{
	string s;
	vector<vector<int>> arr;
	int n;
	while (cin >> s)
	{
		cin >> n;
		for (int i = 0; i < n; i++)
		{
			int n1, n2;
			cin >> n1 >> n2;
			if (n1 > n2)
			{
				int t = n1;
				n1 = n2;
				n2 = t;
			}
			vector<int> tmp;
			tmp.push_back(n1);
			tmp.push_back(n2);
			arr.push_back(tmp);
		}
		getStr(s, arr);
		arr.clear();
		s.clear();
	}
    return 0;
}

#include <iostream>
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
using namespace std;
/*
dcba
2
0 1
1 2
hellonowcoder
4
0 1
1 4
2 5
2 3

bcda
ehllonowcoder

1<=s的长度<=10000

1<=n<=10000
*/
char s[10100];
int charfather[10010];
unsigned char chaflag[10010];
int n;


//查找并查集中的祖先元素
int find(int nodeA,int preNode[]){
	int anceA=preNode[nodeA],tmp;
	//如果他不是根节点，循环，直至找到根节点
	while(anceA != preNode[anceA]){
		anceA = preNode[anceA];
	}
	//压缩并查集，让一课集合内的节点都指向一个根（代表元素）
	while(anceA != preNode[nodeA]){
		tmp = preNode[nodeA];
		preNode[nodeA] = anceA;
		nodeA = tmp;
	}
	return anceA;
}

int main(){
	int tmp1,tmp2,slen,tmp3,tmp4;
	char tmp;
	while(cin>>s){
		slen = strlen(s);
		cin>>n;
		for(int j=0;j<slen;j++){
			charfather[j] =j;
			chaflag[j] = 0;
		}	
		for(int i=0;i<n;i++){
			cin>>tmp1>>tmp2;
			tmp3 = find(tmp1,charfather);
			tmp4 = find(tmp2,charfather);
                //合并并查集
			charfather[tmp3] = tmp4;
			chaflag[tmp1] = 1;
			chaflag[tmp2] = 1;
		}
	
		for(int i = 0;i< slen-1 ;i++){
			if(0 == chaflag[i]){
				continue;
			}
			tmp1 =  find(i,charfather);
			for(int j=i+1;j<slen;j++){
				if(0 == chaflag[j]){
					continue;
				}
				if(s[i] > s[j]  && find(j,charfather) == tmp1){
					tmp = s[i];
					s[i] = s[j];
					s[j] = tmp;
				}
			}
		
		}
		// for(int j = 0 ; j<slen ;j++){
			// cout<<chaflag[j]<<" ";
		// }
		// cout<<endl;
		cout<<s<<endl;
	}
    return 0;
}

import java.util.ArrayList;
import java.util.Scanner;

public class Main{
	/**下面两组测试数据均已通过，然并卵，后台报没有通过所有测试用例。
	 * 是不是我的scanner输入有问题啊
	 * abdc
	 * 2
	 * 0 1
	 * 1 2
	 * abcddd
	 * 5
	 * 0 1
	 * 1 2
	 * 2 3
	 * 4 5
	 * 1 5
	 */
	public static void main(String[] args) {
		
		Scanner in =new Scanner(System.in);
		while (in.hasNext()) {
			String s1=in.next();
			
			int N=in.nextInt();
			in.nextLine();
			ArrayList<int[]> lst=new ArrayList<>();
			for(int i=0;i<N;i++){
				int []tmp=new int[2];
				
				String tmp2=in.nextLine();
				String[] tmp3=tmp2.split(" ");
				tmp[0]=Integer.parseInt(tmp3[0]);
				tmp[1]=Integer.parseInt(tmp3[1]);
				lst.add(tmp);
			}
			System.out.println(compute(s1, lst));
		}
		
	}
	
	/**
	 * 
	 * @param s1:宝石的字符串
	 * @param caihong:list中每个元素都是长度为2的数组
	 * @return
	 */
	public static String compute(String s1,ArrayList<int[]> caihong){

		char[] tmp1=s1.toCharArray();
		char swap ;
		boolean flag1=false;
		
		//flag1为false代表字符串中仍然有不满足字典序的情况
		while (!flag1) {
			//读所有彩虹，判断对应位置的字典序，如果满足条件则交换。
			for(int [] x:caihong){
				if(tmp1[x[0]]>tmp1[x[1]]){
					swap=tmp1[x[0]];
					tmp1[x[0]]=tmp1[x[1]];
					tmp1[x[1]]=swap;
					continue;
				}
				//判断到没有满足字典序情况，便把flag1置true,跳出循环。
				flag1=true;
			}
		}
		
		return String.valueOf(tmp1);
	}
	
}  

importjava.awt.Label;

importjava.util.ArrayList;

importjava.util.Arrays;

importjava.util.Collections;

importjava.util.Comparator;

importjava.util.HashSet;

importjava.util.List;

importjava.util.Scanner;

importjava.util.Set;

importjava.util.HashMap;

importjava.util.Iterator;

importjava.util.Map;

importjava.util.Scanner;

 

publicclassMain

{

     

    publicstaticvoidmain(String[] args)

    {

        Scanner scan=newScanner(System.in);

         

        StringBuffer str=newStringBuffer(scan.next());

        intnum1,num2;

        intn=scan.nextInt();

        intlab[]=newint[str.length()];

        intk=0;

        for(inti=0;i<lab.length;i++)

            lab[i]=-1;

        for(inti=0;i<n;i++)

        {

            num1=scan.nextInt();

            num2=scan.nextInt();

            if((lab[num1]==-1) && (lab[num2]==-1))

                {lab[num1]=k;lab[num2]=k++;}

            elseif(lab[num1]!=-1)

                lab[num2]=lab[num1];

            else

                lab[num1]=lab[num2];

        }

        for(inti=0;i<=k-1;i++)

        {

            ArrayList<Character> list=newArrayList<Character>();

            for(intj=0;j<lab.length;j++)

            {

                if(lab[j]==i)

                    list.add(str.charAt(j));

            }

            intcnt=0;

            Collections.sort(list);

            for(intj=0;j<lab.length;j++)

            {

                if(lab[j]==i)

                    str.replace(j, j+1, String.valueOf(list.get(cnt++)));

            }

        }

        System.out.println(str);

    }

 

}

哪位大神指点下。  没有通过所有测试用例   

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public String deal(ArrayList<String> list, String str) {
		StringBuffer fsb = new StringBuffer(str);
		for (int i = 0; i < list.size(); i++) {
			String s = list.get(i);
			byte[] temps = s.getBytes();
			Arrays.sort(temps);
			s = new String(temps);
			StringBuffer sb = new StringBuffer();
			for (int j = 0; j < s.length(); j++) {
				// 将这些位置上的字符拿出来排序
				int loc = Integer.valueOf(String.valueOf(s.charAt(j)));
				sb.append(str.charAt(loc));
			}
			byte[] b = sb.toString().getBytes();
			Arrays.sort(b);
			String finalstr = new String(b);
			// 按照这些顺序装上去
			for (int j = 0; j < s.length(); j++) {
				// 将这些位置上的字符拿出来排序
				int loc = Integer.valueOf(String.valueOf(s.charAt(j)));
				// loc的位置需要替换成 finalstr.charAt(j)
				fsb.delete(loc, loc + 1);
				fsb.replace(loc, loc, String.valueOf(finalstr.charAt(j)));
			}
		}
		return fsb.toString();
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		int number = Integer.valueOf(sc.nextLine());
		ArrayList<String> list = new ArrayList<String>();
		for (int i = 0; i < number; i++) {
			String l = sc.nextLine();
			String[] s = l.split(" ");
			for (int t = 0; t < list.size(); t++) {
				String string = (String) list.get(t);
				if (list.get(t).contains(s[0])) {
					string = string + s[1];
					list.set(t, string);
					break;
				} else if (list.get(t).contains(s[1])) {
					string = string + s[0];
					list.set(t, string);
					break;
				}
				if (t == list.size() - 1) {
					list.add(s[0] + s[1]);
					break;
				}
			}
			if (list.size() == 0) {
				list.add(s[0] + s[1]);
			}
		}
		Main m = new Main();
		System.out.println(m.deal(list, str));
	}

}
求大神帮我看看，通过不了。。。

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s = in.next();
            int n = in.nextInt();
            int[] ai = new int[n];
            int[] bi = new int[n];
            for (int i = 0; i < n; i++) {
                ai[i] = in.nextInt();
                bi[i] = in.nextInt();
            }
            String min = process(s, ai, bi);
            System.out.println(min);
        }
    }

    /**
     * 并查集
     *
     * @param s
     * @param ai
     * @param bi
     * @return
     */
    private static String process(String s, int[] ai, int[] bi) {
        char[] ch = s.toCharArray();
        int[] pre = new int[s.length()];
        Arrays.fill(pre, -1);
        for (int i = 0; i < ai.length; i++) {
            pre[bi[i]] = ai[i];
            find(pre, bi[i]);
        }
        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            List<Integer> list = new ArrayList<>();
            list.add(i);
            lists.add(list);
            if (pre[i] != -1) {
                lists.get(pre[i]).add(i);
            }
        }
        for (int i = 0; i < lists.size(); i++) {
            List<Integer> list = lists.get(i);
            if (list.size() > 1) {
                List<Character> chars = new ArrayList<>();
                for (int j = 0; j < list.size(); j++) {
                    chars.add(ch[list.get(j)]);
                }
                Collections.sort(chars);
                for (int j = 0; j < list.size(); j++) {
                    ch[list.get(j)] = chars.get(j);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            sb.append(ch[i]);
        }

        return sb.toString();
    }

    private static int find(int[] pre, int x) {
        int res = x;
        while (pre[res] != -1) {
            res = pre[res];
        }
        int cur = x;
        while (cur != res) {
            int temp = pre[cur];
            pre[cur] = res;
            cur = temp;
        }

        return res;
    }
}

//写个简单的C语言的吧！调了好久
#include<stdio.h>
#include<string.h>
#define MAXSIZE 10000
void Swap(char *a,char *b)
{
	char val;
	val = *a;
	*a = *b;
	*b = val;
}
/*
在构造数组的时候忽略了一种情况，就是两个点都与其他点相连
*/
void MakeMatrix(int a[][2],int b[MAXSIZE],int n,int len)
{
	int count = 1;
	int i,j;
	for(i=0;i<len;++i)
	{
		b[i] = 0;
	}
	for(i=0;i<n;++i)
	{
		if(0 == b[a[i][0]] && 0 == b[a[i][1]])
		{
			b[a[i][0]] = b[a[i][1]] = count++;
		}
		else if(b[a[i][0]]!= 0 && 0 == b[a[i][1]])
		{
			b[a[i][1]] = b[a[i][0]];
		}
		else if(b[a[i][0]]== 0 && 0 != b[a[i][1]])
		{
			b[a[i][0]] = b[a[i][1]];
		}
		else
		{
			if(b[a[i][0]] != b[a[i][1]])
			{
				int temp = b[a[i][1]];
				for(j=0;j<len;++j)
				{
					if(b[j] == temp)
					{
						b[j] = b[a[i][0]];
					}
				}
			}
		}
	}

}
void SeleSort(char *array,int b[MAXSIZE],int len)
{
	int i,j,min;
	for(i=0;i<len;++i)
	{
		if(b[i]!=0)
		{
			min = i;
			for(j=i+1;j<len;++j)
			{
				if(b[i] == b[j])
				{
					if(array[min]>array[j])
					{
						min = j;
					}
				}
			}
			if(min!=i)
			{
				Swap(&array[min],&array[i]);
			}
		}
		
	}
}
int main()
{
	char array[MAXSIZE];
	int b[MAXSIZE] = {0};
	int a[MAXSIZE][2];
	int n;
	int len;
	while(EOF!=scanf("%s",array))
	{
		len = strlen(array);
		scanf("%d",&n);
		for(int i=0;i<n;++i)
		{
			scanf("%d%d",&a[i][0],&a[i][1]);
		}
		MakeMatrix(a,b,n,len);
		SeleSort(array,b,len);
		puts(array);
	}
	return 0;
}

//贴出思路： 在输入字符串的下方建立一个等长的数组，记录关联性
//如测试用例中hellonowcoder 0 1 1 4  这两组数据中就表明了 下标为0 1 4 的三个字符需要进行字典序。
//输入一遍后会得出对应的关联数组，根据关联性进行输入list排序。
//本地测试都对。但提交不正确，数据量太大也没有给出具体错误原因。 
//测试用例 h  e  l  l  o  n o w c o  d e r   4   0 1    1 4   2 5  2 3
//关联性数组为     1 1 2 2  1  2  0 0 0 0 0 0 0    014关联  235 关联  然后依次进行字典序 import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.Scanner;

public class test {
	public static void main(String[] strs) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			String initstr = sc.next();
			char[] arr = initstr.toCharArray();
			int n = sc.nextInt();
			int[] index = new int[arr.length]; // 记录字符串下标 下标一样的为一组测试数据
			int num = 1; // 从1开始
			for (int i = 0; i < n; i++) {
				int begin = sc.nextInt(); // 彩虹开始
				int end = sc.nextInt(); // 彩虹结束
				if (index[begin] == 0 && index[end] == 0) {   //如果两个数和其他没有关联性，则加入
					index[begin] = num;
					index[end] = num;
					num++;   //关联性+1
				}else if(index[begin] != 0 && index[end] == 0) {  //找到关联
					index[end]=index[begin];   
				}else if(index[begin] == 0 && index[end] != 0){ //找到关联 index[begin]=index[end];
				}
			}
			ArrayList<Character> list= new ArrayList<Character>();
			int max=0;  //找出有几组关联
			for(int i=0;i<index.length;i++){
				if(max<index[i])
					max=index[i];
			}
			for(int i=1;i<=max;i++){  //从1开始将相关关联的字符放入list集合进行排序
				for(int j=0;j<index.length;j++){
					if(index[j]==i){
						list.add(arr[j]);
					}
				}
				Collections.sort(list);
				Iterator<Character> iterator=list.iterator();  //依次取出
				for(int j=0;j<index.length;j++){
					if(index[j]==i){
						
						arr[j]=iterator.next();
					}
				}
				list.clear();
			}
			System.out.println(String.valueOf(arr));
		}
	}
}

如有大神最后做对了 ，求指导

用Java自己写了一个每读一边就排序一次的方法O(ne)的，n=#node,e=#edge超时。按照第一个人思路把C＋＋重构了弄成Java又写了一遍，复杂度O(n(loge)),还特么超时。坑爹啊现在是歧视Java是吗。。求大神指导
import java.util.*;
public class Main { public static void main (String args[]) {
        Main instance = new Main();  Scanner scan = new Scanner(System.in);  while (scan.hasNext()) {
            String s = scan.next();  Graph graph = new Graph(s);   if(scan.hasNext()) { int count = scan.nextInt();   while(count > 0) { int i = scan.nextInt(), j = scan.nextInt();  if(j < i) graph.sort(j, i);  else graph.connect(i, j);  count--;  }
            }
            System.out.println(String.valueOf(graph.str));  }
    }

} class Graph { char[] str;  int[] connectedComponentsDec; //connectedComponents[i]: previous closest connected node, -1 if such node doesn't exist  int[] connectedComponentsInc;   public Graph(String s) { str = s.toCharArray();  connectedComponentsDec = new int[str.length];  connectedComponentsInc = new int[str.length];  Arrays.fill(connectedComponentsDec, -1); //initialize as none connected  Arrays.fill(connectedComponentsInc, str.length);  } public void connect(int left, int right) { int i =left, j = right;  while(j != i) { //Sort out orders to the left of j    if(connectedComponentsDec[j] > i) {
                j = connectedComponentsDec[j];  } else if(connectedComponentsDec[j] < i) {
                sort(i, j);  if(connectedComponentsDec[j] == -1) { connectedComponentsDec[j] = i;  break;  } int tmp = connectedComponentsDec[j];  j = i;  i = tmp;  }
        }
        i = left; j = right;  while(j != i) { if(connectedComponentsInc[i] < j) {
                i = connectedComponentsInc[i];  } else if(connectedComponentsInc[i] > j) {
                sort(i, j);  if(connectedComponentsInc[i] == str.length) { connectedComponentsInc[i] = j;  break;  } int tmp = connectedComponentsInc[i];  i = j;  j = tmp;  }
        }
    } public void sort(int i, int j) { if(str[i] > str[j]) { char tmp = str[j];  str[j] = str[i];  str[i] = tmp;  }
    }
}

import java.util.Arrays;
import java.util.Scanner;

public class Rainbow {

	static int[] id;
	static int[] size;
	static boolean[] marked;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext())
		{
			String string = sc.next();
			char[] strChar = string.toCharArray();
			//TODO: Initialize id[] array
			System.out.println(strChar.length);
			id = new int[strChar.length];
			size = new int[strChar.length];
			marked = new boolean[id.length];
			// 初始化并查集
			for (int i = 0; i < id.length; i++)
			{
				id[i] = i;
				size[i] = 1;
				marked[i] = false;
			}
			
			// 接收系统输入
			int n = sc.nextInt();
			for (int i = 1; i <= n; i++)
			{
				int p = sc.nextInt();
				int q = sc.nextInt();
				//TODO: Process Each edge
				connect(p, q);
			}
						
			// 处理字符串
			for (int i = 0; i < id.length; i++)
			{
				// 若字符i未处理
				if (marked[i] == false)
				{
					// 获取字符i的根节点id
					int sid = id[i];
					// 初始化待处理字符串数组--即被彩虹相连同一串字符
					char[] sortChar = new char[size[sid]];
					for (int j = i, k = 0; j < id.length; j++) {
						if (id[j] == sid) {
							// 将同一串字符存入sortChar中
							sortChar[k] = strChar[j];
							marked[j] = true;
							k++;
						}
					}
					
					// 对sortChar进行排序
					Arrays.sort(sortChar);
					
					// 将排好序的sortChar填入原字符串中
					for (int j = i, k = 0; j < id.length; j++) {
						if (id[j] == sid)
						{
							strChar[j] = sortChar[k++];	
						}
					}
				}
			}
			
			// 输出字符串
			for (char c : strChar)
				System.out.print(c);
			System.out.println();
		}
		sc.close();
	}
	
	// 连接彩虹
	public static void connect(int p, int q) 
	{
		int pId = id[p];
		int qId = id[q];
		// 将所有qId的彩虹改为pId
		for (int i = 0; i < id.length; i++)
		{
			if (id[i] == qId)
			{
				id[i] = pId;
				size[pId]++;
			}
		}	
	}
}

//实则上可以转化为图问题，建图，用深度优先搜索求连通子图，对连通子图内的结点按字典顺//序排序则可

#include<iostream>
#include<cstring>
#include<vector>
#include <algorithm>
using namespace std;
vector<int> gmap[10000];
vector<char> charList;
vector<int> idxList;
bool visted[10000];
void search(int vec);
string temp;
int main(void){
    while(cin>>temp){
        memset(visted,false,sizeof(visted));
        for(int i=0;i<10000;i++){
            gmap[i].clear();
        }
        int n;
        cin>>n;
        for(int i=0;i<n;++i){
            int u,v;
            cin>>u>>v;
            gmap[u].push_back(v);
            gmap[v].push_back(u);
        }
        for(int i=0;i<temp.size();++i){
            if(!visted[i]){
                search(i);
                sort(charList.begin(),charList.end());
                sort(idxList.begin(),idxList.end());
                for(int j=0;j<idxList.size();j++){
                    temp[idxList[j]] = charList[j];
                }
                charList.clear();
                idxList.clear();
            }
        }
        cout<<temp<<endl;
    }
    return 0;
}
void search(int vec){
    visted[vec] = true;
    idxList.push_back(vec);
    charList.push_back(temp[vec]);
    for(int i=0;i<gmap[vec].size();i++){
        int nextVec = gmap[vec][i];
        if(!visted[nextVec]){
            search(nextVec);
        }
    } }

	#define _CRT_SECURE_NO_WARNINGS



	#include <iostream>



	#include <vector>



	#include <algorithm>



	#include <string>



	using namespace std;



	



	



	int main(){



	string bs, str;



	intn;



	while(cin >> bs){



	cin >> n;



	str = bs;



	



	intind_map[10000];



	for(inti = 0; i < 10000; i++)



	ind_map[i] = -1;



	



	vector<vector<int>>dl;



	vector<int> paths(str.size());



	for(inti = 0; i<str.size(); i++)



	paths[i] = i;



	intm = 0;



	for(inti = 0; i < n; i++)



	{



	longa, b;



	cin >> a >> b;



	



	if(a > b)



	swap(a, b);



	



	if(ind_map[a] != -1)



	{



	if(ind_map[b] != -1&& ind_map[b] != ind_map[a])



	{



	intinda = ind_map[a];



	intindb = ind_map[b];



	for(intj = 0; j < dl[indb].size(); j++)



	{



	dl[inda].push_back(dl[indb][j]);



	ind_map[dl[indb][j]] = inda;



	}



	dl[indb].clear();



	}



	else



	{



	intind = ind_map[a];



	dl[ind].push_back(b);



	ind_map[b] = ind_map[a];



	}



	}



	elseif(ind_map[b] != -1)



	{



	intind = ind_map[b];



	dl[ind].push_back(a);



	ind_map[a] = ind_map[b];



	}



	else



	{



	dl.push_back(vector<int>());



	dl[m].push_back(a);



	dl[m].push_back(b);



	ind_map[a] = m;



	ind_map[b] = m;



	m++;



	}



	}



	



	for(inti = 0; i < m; i++)



	{



	if(!dl[i].empty())



	{



	sort(dl[i].begin(), dl[i].end());



	dl[i].erase(unique(dl[i].begin(), dl[i].end()), dl[i].end());



	string r;



	for(intj = 0; j < dl[i].size(); j++)



	{



	r.push_back(bs[dl[i][j]]);



	}



	sort(r.begin(), r.end());



	for(intj = 0; j < dl[i].size(); j++)



	{



	bs[dl[i][j]] = r[j];



	}



	}



	}



	



	cout << bs << endl;



	}



	return0;



	}



	



	



	



	



	



	
	

		
		

			
			

				#define _CRT_SECURE_NO_WARNINGS
			

			

				#include <iostream>
			

			

				#include <vector>
			

			

				#include <algorithm>
			

			

				#include <string>
			

			

				#include <list>
			

			

				using namespace std;
			

			

				 
			

			

				 
			

			

				voiddfs(vector<int>& res,vector<list<int>> &dl, intind, int*visit)
			

			

				{
			

			

				    visit[ind] = 0;
			

			

				    res.push_back(ind);
			

			

				    for(list<int>::iterator it = dl[ind].begin(); it != dl[ind].end(); it++)
			

			

				    {
			

			

				        if(visit[*it])
			

			

				        {
			

			

				            dfs(res, dl, *it, visit);
			

			

				        }
			

			

				    }
			

			

				}
			

			

				intmain(){
			

			

				    string bs, str;
			

			

				    intn;
			

			

				    //freopen("r.txt", "r", stdin);
			

			

				    while(cin >> bs){
			

			

				        cin >> n;
			

			

				        str = bs;
			

			

				        vector<list<int>>dl(10000);
			

			

				        intvisit[10000] = { 0};
			

			

				 
			

			

				 
			

			

				        vector<int> paths(str.size());
			

			

				        for(inti = 0; i<str.size(); i++)
			

			

				            paths[i] = i;
			

			

				 
			

			

				        for(inti = 0; i < n; i++)
			

			

				        {
			

			

				            longa, b;
			

			

				            cin >> a >> b;
			

			

				            visit[a] = visit[b] = 1;
			

			

				            dl[a].push_back(b);
			

			

				            dl[b].push_back(a);
			

			

				        }
			

			

				        vector<vector<int>> res;
			

			

				        intm = 0;
			

			

				        for(inti = 0; i < str.size(); i++)
			

			

				        {
			

			

				            if(visit[i])
			

			

				            {
			

			

				                res.push_back(vector<int>());
			

			

				                dfs(res[m++], dl, i, visit);
			

			

				            }
			

			

				        }
			

			

				        for(inti = 0; i < res.size(); i++)
			

			

				        {
			

			

				            sort(res[i].begin(), res[i].end());
			

			

				            res[i].erase(unique(res[i].begin(), res[i].end()), res[i].end());
			

			

				            string r;
			

			

				            for(intj=0; j < res[i].size(); j++)
			

			

				            {
			

			

				                r.push_back(bs[res[i][j]]);
			

			

				            }
			

			

				            sort(r.begin(), r.end());
			

			

				            for(intj = 0; j < res[i].size(); j++)
			

			

				            {
			

			

				                bs[res[i][j]] = r[j];
			

			

				            }
			

			

				        }
			

			

				        cout << bs << endl;
			

			

				 
			

			

				    }
			

			

				    return0;
			

			

				}