lp1341 无序字母对

仔细观察这题：考虑到字母对可以反向，我们不妨把它们看作无序数对。这就把题意转化为了，给你n个无序数对，让你找到一个n+1个数的序列，使得无序数对在序列的相邻两项中各自至少出现一次。
观察到这无序数对组和图的相似性，我们可以尝试把无序数对看成一条边，然后建一张图。在这种情况下，这个序列就是这张图上的一个遍历顺序，使得经过每一条边至少一次。
深入考虑，这个序列也只能经过每条边至多一次。这是因为，一条n条边的路径，恰好包含了n+1个点。
问题就转化为了欧拉路径问题。

判断一张图是否是半欧拉图是很容易的。一张半欧拉图中，恰好有两个点的度数为奇数——这两个点各自作为欧拉路径的起点和终点。
求解欧拉回路的方法是很容易的。对于每一个点，我们只需要找到与它相邻的所有环即可。
问题在于——这很不显然——为什么相同的求法放到欧拉路径上，只需从奇数入度点开始，就是合法的？
我们不妨把整个欧拉路径抽象成一条链上面挂着一堆环套环套环套环套环。一个令人好奇的问题是，为什么搜索的时候不会直接走到链的另一端，而是先把环跑完，或者反过来？
我们注意到把点加入答案数组的方式：对于两个栈——答案栈和搜索栈来说，点被加入的顺序是不仅相同的。
模拟一下，一个点能从搜索栈出来，被加入答案栈，当且仅当从这个点出发无路可走了。
显然，有且仅有终点是无路可走的。那么，无论终点是在什么时候被访问到的，只要它被访问到，那么它就会被立刻退出搜索栈并被加入答案栈，剩下的点也是同理。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int hash[200];int hsah[200];
int mp[60][60],in[60];
int n;
int st[3005],tp=0;
inline void dfs(int X){
	for(int i=0;i<52;++i){
		if(mp[X][i]){
			printf("%d %d\n",X,i);
			--mp[X][i],--mp[i][X];
			dfs(i);
		}
	}
	printf("%d\n",X); 
	st[++tp]=X;
}
void init(){
	for(int i=0;i<26;++i){
		hash['A'+i]=i;hash['a'+i]=i+26;
		hsah[i]='A'+i;hsah[i+26]='a'+i;
	}
	scanf("%d",&n);
	char ch[4];
	for(int i=1;i<=n;++i){
		std::cin>>ch+1;
		++mp[hash[ch[1]]][hash[ch[2]]],++mp[hash[ch[2]]][hash[ch[1]]];
		++in[hash[ch[1]]],++in[hash[ch[2]]];
	}
	int ans=0,nans=-1;
	for(int i=0;i<52;++i){
		if(in[i]&1){
			++ans;
			if(nans<0){nans=i;}
		}
	}
	if(ans&&ans!=2){
		puts("No Solution");
		return;
	}
	if(!ans){
		for(int i=0;i<52;++i){
			if(in[i]){
				nans=i;
				break;
			}
		}
	}
	dfs(nans);
	if(tp!=n+1){
		puts("No Solution");
		return;
	}
	while(tp){
		putchar(hsah[st[tp--]]);
	}
}
int main(){
	init();
	return 0;
}