CF1735C_Codeforces Round #824 (Div. 2)C

/*
	题意：
		现有一个26个小写字母形成的环，将一个字符串加密，加密规则为将字母变换为环中该字母顺时针的下一个字母
		现给出加密后的字符串，要求解密出字典序最小的字符串
	分析：
		对于每一个字母tt，按照字典序找到它在环中的前一个字母ss，形成ss->tt 
		需要注意：如果当前字母tt与找到的字母ss已经连通(tt->...->ss)，那么不能 ss->tt这样会形成环，只有在已经有25条->线时，才可以这样连接，形成一个环 
		用并查集来维护已经连接的字母的信息 
*/
#include <bits/stdc++.h>
using namespace std;
const int N=27;
//-------------------------
int cnt, f[N], pre[N], nxt[N]; //pre[i]表示i在环中的前一个字母, nxt[i]表示i在环中的后一个字母---------前后是按照顺时针顺序说的 
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void calc(int x)
{
	//按照字典序找它在环中的前一个字母 
	for(int i=1; i<=26; i++){
		if(i==x)continue; //它的前一个字母不可能为本身
		if(!nxt[i]){ //当i所代表的字母后一个字母没有确定时 
			if(cnt!=25 && find(i)==find(x))continue; //没有25条->，并且i与x本身已经连通，那么不能i->x
			++cnt;
			nxt[i]=x;
			pre[x]=i;
			f[find(i)]=find(x); 
			break;
		} 
	}
}
void solve()
{
	cnt=0; //cnt表示已经连接的 -> 条数 
	int n;
	cin>>n;
	string t;
	cin>>t;
	for(int i=1; i<=26; i++)f[i]=i, pre[i]=0, nxt[i]=0;
	for(int i=0; i<t.size(); i++){
		int x=t[i]-'a'+1;
		if(!pre[x])calc(x); //如果当前字母没有找到它在环中的前一个字母，那么就去找
		putchar(pre[x]+'a'-1); 
	}
	putchar('\n');
}
int main(void)
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T=1;cin>>T;
	while(T--)solve();
	return 0;
}