UOJ #117. 欧拉回路

欧拉回路

有一天一位灵魂画师画了一张图,现在要你找出欧拉回路,即在图中找一个环使得每条边都在环上出现恰好一次。

一共两个子任务:

  1. 这张图是无向图。(50分)
  2. 这张图是有向图。(50分)

输入格式

第一行一个整数 t,表示子任务编号。t∈{1,2},如果 t=1则表示处理无向图的情况,如果t=2 则表示处理有向图的情况。

第二行两个整数 n,m,表示图的结点数和边数。

接下来 m行中,第 i行两个整数 vi,ui表示第 i 条边(从 1 开始编号)。保证 1≤vi,ui≤n。

  1. 如果 t=1则表示 vi到 ui 有一条无向边。
  2. 如果 t=2 则表示 vi到 ui 有一条有向边。

图中可能有重边也可能有自环。

输出格式

如果不可以一笔画,输出一行 “NO”。

否则,输出一行 “YES”,接下来一行输出一组方案。

  1. 如果 t=1,输出 m 个整数 p1,p2,…,pm。令 e=∣pi∣,那么 e 表示经过的第 i 条边的编号。如果 pi为正数表示从 ve走到 ue,否则表示从 ue 走到 ve。
  2. 如果 t=2,输出 m 个整数 p1,p2,…,pm。其中 pi 表示经过的第 i条边的编号。

样例一

input

1
3 3
1 2
2 3
1 3

output

YES
1 2 -3

样例二

input

2
5 6
2 3
2 5
3 4
1 2
4 2
5 1

output

YES
4 1 3 5 2 6

限制与约定

1≤n≤105,0≤m≤2×105

时间限制:1s

空间限制:256MB

下载

当图是无向图时,欧拉回路的存在条件为所有点的入度为偶数

当图是有向图时,欧拉回路的存在条件是所有点的入度等于出度

求欧拉回路时dfs所有边

回溯时存下所有边

然后倒叙输出

UOJ的数据真是坑,自环重边漫天飞QWQ、、、

还有GG();写成GG;居然不报错QWQ。、

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int MAXN=1e6+10;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20+1,stdin),p1==p2)?EOF:*p1++)
char buf[1<<20+1],*p1=buf,*p2=buf;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int N,M,S;
struct node
{
    int u,v,ID,nxt;
}edge[MAXN];
int head[MAXN],num=1;
int inder[MAXN],ans[MAXN],vis[MAXN],tot=0;
inline void AddEdge(int x,int y,int z)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].ID=z;
    edge[num].nxt=head[x];
    head[x]=num++;
}
void GG(){printf("NO");exit(0);}
int dfs(int now)
{
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(!vis[abs(edge[i].ID)])
        {
            head[now]=i;
            vis[abs(edge[i].ID)]=1,dfs(edge[i].v);
            ans[++tot]=edge[i].ID;
            i=head[now];    
        }
    }
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    memset(head,-1,sizeof(head));
    int QWQ=read();
    if(QWQ==1)
    {
        N=read();M=read();
        for(int i=1;i<=M;i++)
        {
            int x=read(),y=read();S=x;
            AddEdge(x,y,i);
            AddEdge(y,x,-i);
            inder[x]++;inder[y]++;
        }
        for(int i=1;i<=N;i++)
            if(inder[i]&1) GG();
        dfs(S);
        if(tot<M) GG();
        puts("YES");
        for(int i=M;i>=1;i--)
            printf("%d ",ans[i]);
    }
    else
    {
        N=read();M=read();
        for(int i=1;i<=M;i++)
        {
            int x=read(),y=read();S=x;
            AddEdge(x,y,i);
            inder[y]--;inder[x]++;
            S=x;
        }
        for(int i=1;i<=N;i++)
            if(inder[i]!=0)
                GG();
        dfs(S);
        if(tot<M) GG();
        puts("YES");
        for(int i=M;i>=1;i--)
            printf("%d ",ans[i]);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏李家的小酒馆

图论基本知识

图 图的基本概念 图示一个复杂的结构,节点之间的关系可以是任意的,图中的任意两个元素之间都可能相关。 ? 图分为有向图和无向图,无向图为两个节点之间互相可以到达...

21800
来自专栏云霄雨霁

加权有向图----加权有向图的实现

22600
来自专栏LhWorld哥陪你聊算法

Hadoop源码篇--Reduce篇

Reduce文件会从Mapper任务中拉取很多小文件,小文件内部有序,但是整体是没序的,Reduce会合并小文件,然后套个归并算法,变成一个整体有序的文件。

28010
来自专栏用户画像

5.2.4 邻接多重表

在邻接表中,容易求得顶点和边的各种信息,但在邻接表中求两个顶点之间是否存在边,或需要对边执行删除等操作时,需要分别在两个顶点的边表中遍历,效率较低。

11510
来自专栏小鹏的专栏

How to pass an array from C++ to an embedded python

细节问题可以查看: ubuntu下C++如何调用python程序,gdb调试C++代码 下面是C++调用Python二维数组传递的问题: #define ...

28190
来自专栏鸿的学习笔记

写给开发者的机器学习指南(十二)

此代码加载DJI数据,并将其添加到已经包含我们自己的股票市场指数的图形上。但是,当我们执行这段代码时,结果如下。

11520
来自专栏张俊红

数据结构-图

图是不同于前面两种数据结构的另一种新的数据结构,线性表中元素与元素之间是被串起来的,每个数据元素只有一个直接前驱和一个直接后继,是一种一对一的数据结构;在树的结...

39610
来自专栏JetpropelledSnake

Django学习笔记之Django ORM Aggregation聚合详解

在当今根据需求而不断调整而成的应用程序中,通常不仅需要能依常规的字段,如字母顺序或创建日期,来对项目进行排序,还需要按其他某种动态数据对项目进行排序。Djngo...

10520
来自专栏C语言及其他语言

优秀题解【图的遍历——深度优先搜索】

解题思路: (1)总思路:在图中任意选取一个顶点开始(题目要求编号为0开始),访问该顶点,并把该顶点设置为已访问

9420
来自专栏Albert陈凯

2018-04-17 Java的Collection集合类3分钟搞掂Set集合前言

3分钟搞掂Set集合 前言 声明,本文用的是jdk1.8 现在这篇主要讲Set集合的三个子类: HashSet集合 A:底层数据结构是哈希表(是一个元素为链...

30670

扫码关注云+社区

领取腾讯云代金券