首页 > 代码库 > SPOJ LEXSTR 并查集

SPOJ LEXSTR 并查集

2024-09-06 20:20:41   216人阅读

题目描述：

Taplu and Abhishar loved playing scrabble. One day they thought of inventing a new game using alphabet tiles. Abhishar wrote a string using tiles and gave a set of pairs (i,j) to Taplu.

Pair “i, j” (0 based indexing) means that Taplu can swap the i’th and j’th tile in the string any number of times.  

He then asks Taplu to give the lexicographically smallest string that can be produced by doing any number of swaps on the original string.

Input

First line contains T(1<=T<=10), the number of testcases.

First line of each test case contains the initial string S. Length of Sttring is len(1<=len<=100000).

Next line contains the number of pairs M (1<=M<=100000).

Next M lines contains pairs i j that means ith character can be swapped with jth character.

Note - i and j can be same and same i,j pair can occur twice.

 

Output

For each testcase output the lexicographically smallest string that can be made from the initial string.

Example

Input:

1
lmaf
3
0 1
1 2
2 3

Output:
aflm

题目的意思是给你一个字符串，然后给你n对位置，每一对位置上的两个字符可以进行无数次交换，问你进行足够多的交换后，你能得到的最小字典序的字符串是什么？

如果想到并查集的话，就是把这n对位置进行集合上的合并，然后就变成了几个集合，这几个集合里面存的是一堆位置，在同一集合的位置能互换。
现在我们只要每个集合中位置所对应的字符按照字典序排个序，每个集合都满足字典序最小，这样整体拼起来就也应该是最小的字典序。

代码如下:
 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 const int maxn =100800;
 5 vector<char> e[maxn];
 6 char s[maxn];
 7 int h[maxn];
 8 int father[maxn],l;
 9 int t,n;
10 int Find(int x)
11 {
12     if (father[x]==x)
13         return x;
14     return father[x]=Find(father[x]);
15 }
16 void Union (int x,int y)
17 {
18     int fx=Find(x),fy=Find(y);
19     if (fx!=fy);
20     father[fx]=fy;
21 }
22 void init()
23 {
24     for (int i=0;i<maxn;++i)
25         e[i].clear();
26     memset(h,0,sizeof h);
27     for (int i=0;i<maxn;++i)
28         father[i]=i;
29 }
30 int main()
31 {
32     //freopen("de.txt","r",stdin);
33     scanf("%d",&t);
34     while (t--){
35         init();
36         scanf("%s",s+1);
37         l=strlen(s+1);
38         scanf("%d",&n);
39         for (int i=0;i<n;++i){
40             int a,b;
41             scanf("%d%d",&a,&b);
42             Union(++a,++b);
43         }
44         for (int i=1;i<=l;++i)
45             e[Find(i)].push_back(s[i]);//将对应位置的字符加入vector,以便排序
46         for (int i=1;i<=l;++i)
47             sort(e[i].begin(),e[i].end());//将每个集合中的字母排序
48         for (int i=1;i<=l;++i){
49             int tmp=Find(i);//找到当前位置所在集合的代表元素
50             printf("%c",e[tmp][h[tmp]++]);//输出当前集合的h[tmp]++个元素，h[]数组用于统计集合内已经输出了几个元素
51         }
52         printf("\n");
53     }
54     return 0;
55 }

 



SPOJ LEXSTR 并查集


联系
我们