POJ 2337 Catenyms（有向图的欧拉通路）

题意：给n个字符串（3<=n<=1000），当字符串str[i]的尾字符与str[j]的首字符一样时，可用dot连接。判断用所有字符串一次且仅一次，连接成一串。若可以，输出答案的最小字典序（dot是最小字典序的，比‘a'小）。

显然就是以26个字母为结点，n个字符串为边，求解有向图的欧拉通路。

不过这里要注意，26个字母不一定都用上。

先判断有向图的欧拉通路的条件是否成立：

1.有一个结点入度等于出度+1且有一个结点出度等于入度+1且其他结点入度等于出度。（或所有结点入度等于出度）

2.有向图的基图连通。（把有向边改成无向边后，图连通）

感觉中间那段while（top）可以当做模板来用了，具体机理这里不详细说了，看着想一想还是能理解的。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <set>

#include <queue>

#include <map>

#include <stack>

using namespace std;

#define MP make_pair

#define ll long long

#define inf 0x3f3f3f3f

int in[30],out[30];

struct Edge{

	int v,nxt;

	bool vis;

}e[1010];

int head[30],esz;

void addedge(int u,int v){

	e[esz].v=v,e[esz].nxt=head[u];

	e[esz].vis=false;

	head[u]=esz++;

}

int fa[30];

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

bool jud(){

	for(int i=0;i<26;++i) fa[i]=i;

	int st;

	for(int u=0;u<26;++u){

		for(int j=head[u];j!=-1;j=e[j].nxt){

			int v = e[j].v;

			st = fa[find(u)] = find(v);

		}

	}

	for(int i=0;i<26;++i){

		if(out[i]+in[i] && find(i)!=find(st)) return false;

	}

	return true;

}

int main(){

	int t,n;

	scanf("%d",&t);

	while(t--){

		scanf("%d",&n);

		string s[1010];

		for(int i=0;i<n;++i){

			char tmp[22];

			scanf("%s",tmp);

			s[i] = tmp;

		}

		sort(s,s+n);

		memset(in,0,sizeof(in));

		memset(out,0,sizeof(out));

		queue<string>val[30][30];

		esz=0; memset(head,-1,sizeof(head));

		for(int i=n-1;i>=0;--i){

			int u = s[i][0]-'a', v = s[i][s[i].size()-1]-'a';

			out[u]++; in[v]++;

			addedge(u,v);

		}

		for(int i=0;i<n;++i){

			int u = s[i][0]-'a', v = s[i][s[i].size()-1]-'a';

			val[u][v].push(s[i]);

		}

		int j1=-1,j2=-1,j3=1;

		for(int i=0;i<26;++i){

			if(in[i]==out[i]) continue;

			if(out[i]==in[i]+1){

				if(j1==-1) j1=i;

				else j3=0;

				continue;

			}

			if(in[i]==out[i]+1){

				if(j2==-1) j2=i;

				else j3=0;

				continue;

			}

			j3=0;

		}

		if((j1^j2)<0) j3=0;

		if(j3==0 || jud()==false){

			puts("***");

			continue;

		}

		if(j1==-1){

			for(int i=0;i<26;++i){

				if(out[i]){

					j1=i;

					break;

				}

			}

		}

		stack<int>st;

		vector<int>ans;

		st.push(j1);

		while(!st.empty()){

			int u = st.top(); st.pop();

			bool f = false;

			for(int i=head[u];i!=-1;i=e[i].nxt){

				int v = e[i].v;

				if(e[i].vis) continue;

				e[i].vis = true;

				st.push(u);

				st.push(v);

				f=true;

				break;

			}

			if(f==false) ans.push_back(u);

		}

		for(int i=ans.size()-1;i;--i){

			int u = ans[i];

			int v = ans[i-1];

			printf("%s",val[u][v].front().c_str());

			val[u][v].pop();

			if(i!=1) printf(".");

			else puts("");

		}

	}

	return 0;

}