【模板题】欧拉回路-白红宇

【模板题】欧拉回路

阅读量：4677 次

发布时间：2019-06-09

本文共 3216 字，大约阅读时间需要 10 分钟。

题目描述

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

一共两个子任务：

这张图是无向图。（50分）

这张图是有向图。（50分）

输入格式

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

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

接下来 $m$ 行中，第 $i$ 行两个整数 $v_i, u_i$，表示第 $i$ 条边（从 $1$ 开始编号）。保证 $1 \leq v_i, u_i \leq n$。

如果 $t = 1$ 则表示 $v_i$ 到 $u_i$ 有一条无向边。

如果 $t = 2$ 则表示 $v_i$ 到 $u_i$ 有一条有向边。

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

输出格式

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

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

如果 $t = 1$，输出 $m$ 个整数 $p_1, p_2, \dots, p_m$。令 $e = \lvert p_i \rvert$，那么 $e$ 表示经过的第 $i$ 条边的编号。如果 $p_i$ 为正数表示从 $v_e$ 走到 $u_e$，否则表示从 $u_e$ 走到 $v_e$。

如果 $t = 2$，输出 $m$ 个整数 $p_1, p_2, \dots, p_m$。其中 $p_i$ 表示经过的第 $i$ 条边的编号。

样例一

input

13 31 22 31 3

output

YES1 2 -3

样例二

input

25 62 32 53 41 24 25 1

output

YES4 1 3 5 2 6

限制与约定

$1 \leq n \leq 10^5, 0 \leq m \leq 2 \times 10^5$

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$

模板题...不过，我没写过欧拉回路....所以也调了好久的样子

主要的思想就是先找一个简单的环，然后从环上的个点在在向外拓展新的环，然后把答案合并在一起倒叙输出

无向图和有向图唯一的不同就是，有向图只需要把操作过的边删掉即可，而无向图需要删除两条边，所以稍微会麻烦一点...

还有一个教训就是不要用vector的eraser，他的复杂度好像是$O(n)$啊？

#include
    
       #include
     
        #include
      
         #include
       
          #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #define LL long long using namespace std; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; } return *p1++;} inline void read(int &x){ char c=nc();int b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;}int wt,ss[19];inline void print(int x){ if (x<0) x=-x,putchar('-'); if (!x) putchar(48); else { for (wt=0;x;ss[++wt]=x%10,x/=10); for (;wt;putchar(ss[wt]+48),wt--);}}int T,n,m,p,d[100010],ru[100010],chu[100010],ans[200010],h[100010];vector
               
                 b;struct data{ int x,id; data(int a=0,int b=0):x(a),id(b){}};vector
                 a[100010];bool v[200010];void dfs1(int x,int y){ if (a[x].size()>h[x]) { while (v[abs(a[x][h[x]].id)]) { h[x]++; if (h[x]==a[x].size()) break; } if (a[x].size()>h[x]) { int i=a[x][h[x]].x,j=a[x][h[x]].id; h[x]++;v[abs(j)]=1; if (i!=y) dfs1(i,y); ans[++p]=j; } } if (a[x].size()>h[x]) { while (v[abs(a[x][h[x]].id)]) { h[x]++; if (h[x]==a[x].size()) break; } if (a[x].size()>h[x]) dfs1(x,x); }}void dfs2(int x,int y){ if (a[x].size()>h[x]) { int i=a[x][h[x]].x,j=a[x][h[x]].id; h[x]++; if (i!=y) dfs2(i,y); ans[++p]=j; } if (a[x].size()>h[x]) dfs2(x,x);}int main(){ read(T); if (T==1) { read(n);read(m); int x,y; for (int i=1;i<=m;i++) read(x),read(y),d[x]++,d[y]++,a[x].push_back(data(y,i)),a[y].push_back(data(x,-i)); x=0; for (int i=1;i<=n;i++) if (d[i]%2==1) {puts("NO");return 0;} else if (d[i]>0) x=i; memset(h,0,sizeof(h)); p=0;dfs1(x,x); if (p
                 
                  1;i--) print(ans[i]),putchar(' '); if (m>0) print(ans[1]),puts(""); } else if (T==2) { read(n);read(m); int x,y; for (int i=1;i<=m;i++) read(x),read(y),chu[x]++,ru[y]++,a[x].push_back(data(y,i)); x=0; for (int i=1;i<=n;i++) if (ru[i]!=chu[i]) {puts("NO");return 0;} else if (ru[i]>0) x=i; memset(h,0,sizeof(h)); p=0;dfs2(x,x); if (p
                  
                   1;i--) print(ans[i]),putchar(' '); if (m>0) print(ans[1]),puts(""); } return 0;}

转载于:https://www.cnblogs.com/xiejiadong/p/6762530.html

你可能感兴趣的文章

算法导论第6部分图算法，第22章图的基本算法