`
Coco_young
  • 浏览: 125754 次
  • 性别: Icon_minigender_1
  • 来自: 湖南长沙
社区版块
存档分类
最新评论

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;
}
0
0
分享到:
评论
1 楼 Flywarrior 2012-05-30  
很喜欢楼主的编程风格,学习了。

相关推荐

    poj_1699.rar_1699_poj_poj1699

    【标题】"poj_1699.rar_1699_poj_poj1699" 提供的是一个关于POJ(编程在线判题系统)第1699题的解决方案,其中包含了该问题的代码实现和解题思路。POJ是一个流行的在线编程竞赛平台,它为参赛者提供了各种算法题目,...

    poj2775.rar_poj_poj 27_poj27_poj2775

    标签"poj poj_27 poj27 poj2775"进一步确认了这是一道关于POJ平台的编程挑战,其中"poj_27"可能是表示第27类问题或者某种分类,而"poj27"可能是对"poj2775"的简写。 压缩文件中的"www.pudn.com.txt"可能是一个链接...

    poj_2682(3).rar_C++ 数组扩充_poj 26_poj 2682_poj26

    标题中的"poj_2682(3).rar"是一个指向编程竞赛问题的引用,通常这类问题在网站如POJ(Programming Online Judge)上出现,供程序员解决并提交代码进行测试。这个问题的编号是2682,可能涉及到特定的数据结构或算法...

    Poj_1102_.rar_poj11

    标题"Poj_1102_.rar_poj11"暗示了这是一个关于解决Poj_1102问题的资源包,通常在编程竞赛或在线判题系统如POJ(Problem Set of Judge Online)上遇到。POJ是中国的一个在线编程训练平台,提供了各种算法题目供用户...

    POJ_3131.zip_POJ 八数码_poj

    标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...

    poj_3613解题报告

    2遍dp poj_3613解题报告 poj_3613解题报告

    poj_3310.rar_3310_poj

    【标题】"poj_3310.rar_3310_poj"是一个与编程竞赛相关的压缩包,其中包含了对POJ(Problem Online Judge)3310问题的解决方案和详细解析。POJ是一个著名的在线编程竞赛平台,提供各种算法题目供参赛者练习和提交...

    ACM.zip_ACM_poj_poj3187_poj3669

    题目poj3187和poj3669涉及的具体内容无法直接得知,但根据ACM竞赛的特点,它们可能涉及经典的算法问题,如动态规划、贪心算法、图论、字符串处理、排序算法等。 描述中提到“已经测试过可以通过oj”,这意味着提供...

    1010_stamps.zip_1010_POJ 1010_poj_poj stamps_poj10

    《POJ 1010 Stamps:解题思路与陷阱分析》 POJ 1010,也被称为“邮票问题”,是编程竞赛中的一道经典题目,旨在考察参赛者的动态规划和数学思维能力。这个题目在编程爱好者中具有较高的知名度,因为它涉及到有趣的...

    pku_poj_2187.rar_poj 2187_凸包问题

    标题中的“pku_poj_2187.rar_poj 2187_凸包问题”表明这是一个关于北京大学(Peking University, PKU)编程竞赛平台POJ上的第2187题,题目主要涉及凸包问题。描述中的“O(nlogn)凸包问题 poj2187”提示我们解决这个...

    poj_1002_487.rar_poj 1002

    【标题】"poj_1002_487.rar_poj 1002"指的是北京大学在线编程平台上的第1002道题目,这道题目涉及到计算机科学中的算法设计与实现,特别是字符串处理和哈希映射。在这个问题中,我们需要编写一个程序,该程序能够...

    POJ3277.rar_3277 poj_poj3277_多个面积_线段树

    标题中的“POJ3277.rar_3277 poj_poj3277_多个面积_线段树”是指一个与编程竞赛相关的压缩文件,特别提到了POJ(Problemset Online Judge)的第3277号问题。POJ是一个著名的在线编程竞赛平台,参与者需要解决各种...

    poj1990.rar_POJ 19_poj_poj19

    《POJ 1990:树状数组解题策略详解》 在编程竞赛的世界里,POJ(Programming Online Judge)是一个备受瞩目的在线评测系统,它提供了丰富的编程题目供参赛者挑战。其中,编号为1990的题目是一道涉及数据结构与算法...

    C_(POJ_1854)(分治).cpp

    C_(POJ_1854)(分治).cpp

    D_(POJ_1723)(思维)(sort).cpp

    D_(POJ_1723)(思维)(sort).cpp

    jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c

    标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...

    POJ_keptsl6_C++_

    标题“POJ_keptsl6_C++_”表明这是一个关于编程竞赛(POT, Problem Set of Judges)的资源,特别关注C++语言的解决方案。这些竞赛通常涉及到算法设计和实现,以解决各种计算机科学问题。"keptsl6"可能是用户特定的标记...

    D_(POJ_1723)(思维)(第k大数).cpp

    D_(POJ_1723)(思维)(第k大数).cpp

    POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】

    《POJ3009-Curling 2.0:深度优先搜索、向量、回溯与剪枝的综合应用》 北京大学在线编程平台上的POJ3009题目名为"Curling 2.0",它是一道涉及到算法与数据结构的复杂问题,主要考察了参赛者对深度优先搜索(DFS)、...

    欧拉回路题集

    ### 欧拉回路题集解析 #### 欧拉回路概念 欧拉回路(Eulerian Circuit)是指在一个无向图或有向图中,如果存在一条闭合路径,该路径通过每条边恰好一次,则这条路径称为欧拉回路。一个能够包含欧拉回路的图称为...

Global site tag (gtag.js) - Google Analytics