【例题】一笔画问题

链接：http://ybt.ssoier.cn:8088/problem_show.php?pid=1341

时间限制: 1000 ms         内存限制: 65536 KB

如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。

根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行dfs，时间复杂度为O(m+n)，m为边数，n是点数。

 

【输入】

第一行n，m，有n个点，m条边，以下m行描述每条边连接的两点。

【输出】

欧拉路或欧拉回路,输出一条路径即可。

 

【输入样例】

5 51 22 33 44 55 1

【输出样例】

1 5 4 3 2 1

题解：

1. 欧拉通路、欧拉回路、欧拉图

无向图：

1) 设G是连通无向图，则称经过G的每条边一次并且仅一次的路径为欧拉通路；

2) 如果欧拉通路是回路（起点和终点是同一个顶点），则称此回路为欧拉回路（Euler circuit）；

3) 具有欧拉回路的无向图G称为欧拉图（Euler graph）。

有向图：

1) 设D是有向图，D的基图连通，则称经过D的每条边一次并且仅一次的有向路径为有向欧拉通路；

2) 如果有向欧拉通路是有向回路，则称此有向回路为有向欧拉回路（directed Euler circuit）；

3) 具有有向欧拉回路的有向图D称为有向欧拉图（directed Euler graph）。

2. 定理及推论

无向图G存在欧拉通路的充要条件是：

1）G为连通图，并且G仅有两个奇度结点（度数为奇数的顶点）或者无奇度结点

2)  当G是无奇度结点的连通图时，G必有欧拉回路。

3)  G为欧拉图（存在欧拉回路）的充分必要条件是G为无奇度结点的连通图。

注意：一定要后存边，不然遇到一条死路（因为先走小点），顺序不一样

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int n,m,N,t,cur[10005],d[10005];bool g[10005][10005];void print(){    for(int i=1;i
          
           >n>>m;    for(int i=1;i<=m;i++)    {        int u,v;        cin>>u>>v;        g[u][v]=g[v][u]=1;        d[u]++;d[v]++;        N=max(N,u);        N=max(v,N);    }    int start = 1;    for(int i=1;i<=N;i++)        if(d[i]%2)            {start=i;break;}        dfs(start);    print();        }