POJ_2337_欧拉回路+贪心

题目链接：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;
}

评论

1 楼 Flywarrior 2012-05-30  

很喜欢楼主的编程风格，学习了。