poj2337_单词接龙欧拉回路

整整一天都在弄这个 ，终于AC了 。

需要注意的地方都在代码注释里了！

 

 

#include<iostream>   
#include<cstdio>   
#include<string>   
#include<algorithm>  
using namespace std;
#define EMAX 1030
int t,n;
int num;//记录边数目
int vis[30];
int head[EMAX];
int next[EMAX];
int fa[30];
int in[30];
int out[30];
int stk[EMAX];//记录打印顺序
int top;
string str[EMAX];
struct node
{
	int u;//起点
	int v;//终点
	string s;
	int flag;
};
node edge[EMAX];
int num1,num2;

void init()
{
	num=0;
	top=0;
	memset(in,0,sizeof(in));
	memset(out,0,sizeof(out));
	memset(vis,0,sizeof(vis));
	memset(head,-1,sizeof(head));
	memset(next,-1,sizeof(next));
	for(int i=0;i<30;i++)
		fa[i]=i;
	
}

//添加边的方法
void addnode(int u,int v,string s)
{
	edge[num].u=u;
	edge[num].v=v;
	edge[num].s=s;
	edge[num].flag=0;
	next[num]=head[u];
	head[u]=num++;
}

//find 
int find(int a)
{
	if(a==fa[a])
		return a;
	else 
		return fa[a]=find(fa[a]);
}

bool cmp(string a,string b)
{     
	return a>b; //因为是用头插法建立节点 所有必须从大到小排序
	
}  

int iseuler()
{
	// 第一个条件
	int fnum=0;
	int i;
	for(i=1;i<=26;i++)
		if(vis[i]&&find(i)==i)
			fnum++;
		if(fnum>1)
			return 0;
		//第二个条件
		num1=num2=0;
		for(i=1;i<=26;i++)
			if(vis[i]&&in[i]!=out[i])
			{
				if(in[i]-out[i]==1)
					num1++;
				else if(out[i]-in[i]==1)
					num2++;
				else 
					return 0;
			}
			if(num1==1&&num2==1)
				return 1;
			if(num1==0&&num2==0)
				return 1;
			return 0;
}

void dfs(int from)
{
	for(int i=head[from];i!=-1;i=next[i])
	{
		if(!edge[i].flag)
		{
			edge[i].flag=1;
			dfs(edge[i].v);
			stk[top++]=i;
	
		}
	}
}

int main()
{
	//freopen("in.txt","r",stdin);
	scanf("%d",&t);
	
	while(t--)
	{
		int i;
		scanf("%d",&n);
		init();//初始化
		for(i=0;i<n;i++)
		{
		//	scanf("%s",str[i]);
			cin>>str[i];
		}
		
		//排序
		sort(str,str+n,cmp);
		for(i=0;i<n;i++)
		{
			int u=str[i][0]-'a'+1;//顶点从1到26
			int v=str[i][(str[i].length())-1]-'a'+1;
			vis[u]=1;
			vis[v]=1;
			out[u]++;
			in[v]++;
			if(find(u)!=find(v))
				fa[find(v)]=find(u);
			
			addnode(u,v,str[i]);//边从0到num
		}
		if(iseuler())
		{
			int start;//起点的选择：如果是欧拉通路 则选择出度比入度大一的那个点，
			//否则选字典序最小的那个点!!  这点很重要!
			
			//选择入口
			if(num1==1&&num2==1)
			{
				for(int k=0;k<num;k++)
				{
					if(out[edge[k].u]-in[edge[k].u]==1)
					{
						start=k;
						break;
					}
				}
			}
			else 
			{
				start=num-1;//选字典序最小的那个dian 
			}
			dfs(edge[start].u);
			for(i=num-1;i>0;i--)
				cout<<edge[stk[i]].s<<".";
			cout<<edge[stk[i]].s<<endl;
		}
		else
		{
			printf("***\n");
		}
		
	}
	return 0;
}

 因为该题要按字典序输出，我就再这里WA了好久 ，，一开始我是将各个字符串从小到大排序，而我采用的是头插法建立节点。这样同一起点的单词 不一定会按照从小到大的排序的。 如ab aba 。所以应该从大到小排序。

还有一点要注意的是

选择起点：如果是欧拉通路选择出度比入度大一的点，如果是回路，则选择字典序最小的那个点，以它为入口