题目链接:http://poj.org/problem?id=2337
欧拉回路相关定理:
1 无向图为欧拉图,当且仅当为连通图且所有顶点的度为偶数。
2 无向图为半欧拉图,当且仅当为连通图且除了两个顶点的度为奇数之外,其它所有顶点的度为偶数。
3 有向图为欧拉图,当且仅当的基图连通,且所有顶点的入度等于出度。(忽略有向图所有边 的方向,得到的无向图称为该有向图的基图。)
4 有向图为半欧拉图,当且仅当的基图连通,且存在顶点的入度比出度大1、的入度比出度小1,其它所有顶点的入度等于出度。
以上定理用于判断图是否为欧拉图。
求出一条欧拉回路(路径)的算法:
时间复杂度O(E)
Procedure Euler-circuit (start);
Begin
For 顶点start的每个邻接点v Do
If 边(start,v)未被标记 Then Begin
将边(start,v)作上标记;
将边(v,start)作上标记; //1
Euler-circuit (v);
将边加入栈;
End;
End;
最后依次取出栈每一条边而得到图的欧拉回路。(上述伪代码为无向图的,如果是有向图,把//1的那行去掉即可)
(注意,求欧拉道路时,如果是无向图,要从度数为奇数的点出发,如果是有向图,要从出度比入度大1的点出发)
结合该题,要求字典序最小的欧拉回路(道路),那么可以采取如下方式,以单词为边建立有向图,以邻接表的形式存储图,对于每个顶点,把从其出去的边按字典升序排列,如果存在回路,从a-z中最小的顶点出发,按照上述算法求欧拉回路,如存在道路,那么就从固定点出发,如此可以求出字典序最小的回路(道路)
代码如下:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
#include<cstdlib>
using namespace std;
struct node//graph's node
{
int v,vis;
char str[21];
node()
{
vis = 0;
v = -1;
}
bool operator < (const node &n) const
{
return strcmp(str,n.str)<0;
}
};
const int MAXN = 26;
vector<node> g[MAXN];
stack<char*> S;
int used[MAXN],p[MAXN],in[MAXN],out[MAXN];
void addEdge(char *str)
{
int l = strlen(str)-1;
int u = str[0]-'a',v = str[l]-'a';
node edge;
edge.v = v;
strcpy(edge.str,str);
g[u].push_back(edge);
}
void edgesort()
{
for(int i=0;i<26;i++)if(used[i])
{
sort(g[i].begin(),g[i].end());
}
}
void init()
{
memset(used,0,sizeof(used));
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
for(int i=0;i<MAXN;i++)p[i]=i,g[i].clear();
while(!S.empty())S.pop();
}
int find(int x)
{
return x==p[x]?x:p[x]=find(p[x]);
}
void merge(int x,int y)
{
int r1 = find(x),r2 = find(y);
if(r1==r2)return;
p[r1] = r2;
}
bool conn()
{
int cnt = 0 ;
for(int i=0;i<26;i++)
{
if(used[i]&&p[i]==i)cnt++;
}
return cnt==1;
}
bool euler_formula(int &id)
{
int cnt_big=0,cnt_less=0;id = -1;
for(int i=0;i<26;i++)
{
if(used[i])
{
if(in[i]==out[i])continue;
if(in[i]-out[i]==1)cnt_big++;
else if(in[i]-out[i]==-1)cnt_less++,id=i;
else return 0;
}
}
if(!cnt_big&&!cnt_less)return 1;
if(cnt_big==1&&cnt_less==1)return 1;
return 0;
}
void euler_path(int u)
{
for(int i=0;i<g[u].size();i++)
{
int v = g[u][i].v;
if(!g[u][i].vis)
{
g[u][i].vis = 1;
euler_path(v);
S.push(g[u][i].str);
}
}
}
void print_path()
{
char *str = S.top();
S.pop();
printf("%s",str);
while(!S.empty())
{
str = S.top();S.pop();
printf(".%s",str);
}
printf("\n");
}
int main()
{
int t,n;char str[21];
scanf("%d%*c",&t);
while(t--)
{
scanf("%d%*c",&n);
init();
for(int i=0;i<n;i++)
{
scanf("%s%*c",str);
addEdge(str);
int l = strlen(str)-1;
int u = str[0]-'a',v = str[l]-'a';
used[u]=used[v]=1;
out[u]++,in[v]++;
merge(u,v);
}
int id;
bool ok = euler_formula(id)&&conn();
edgesort();
if(ok)
{
if(id==-1)
{
for(int i=0;i<26;i++)
{
if(used[i])
{
euler_path(i);
break;
}
}
}
else euler_path(id);
print_path();
}
else
{
printf("***\n");
}
}
return 0;
}
分享到:
相关推荐
2遍dp poj_3613解题报告 poj_3613解题报告
poj题目2775文件子目录源代码,递归经典题目,
poj典型题目解题思路详解 包含源代码和解题时应注意的问题及题目陷阱设计分析
poj 1699的代码和方法说明,个人原创
C_(POJ_1854)(分治).cpp
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
D_(POJ_1723)(思维)(sort).cpp
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
D_(POJ_1723)(思维)(第k大数).cpp
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
O(nlogn)凸包问题 poj2187
Catenyms poj hoj 欧拉回路输出路径
POJ 3131 双向BFS解立体八数码问题
poj两道题的c++实现。已经测试过可以通过oj
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ题目及算法,包括动态规划、深搜广搜等算法。含相关注释。