欧拉(回)路

DFS求连通图路径（模板）

无向图是特殊的有向图

欧拉回路是特殊的欧拉路

无向图

#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;

int n, m;
int cnt[N];
int tot, ans[N];
bool mp[N][N];

void DFS(int num)
{
    for(int i = 1; i <= n; ++i)
        if(mp[num][i])
        {
            mp[num][i] = mp[i][num] = 0;
            DFS(i);
            ans[++tot] = i;
        }
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        memset(cnt, 0, sizeof(cnt));
        memset(ans, 0, sizeof(ans));
        memset(mp, 0, sizeof(mp));
        tot = 0;
        int u, v;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d", &u, &v);
            mp[u][v] = mp[v][u] = 1;
            cnt[u]++, cnt[v]++;
        }
        int start = 0;
        bool flag = 0;
        for(int i = 1; i <= n; ++i)
        {
            if(cnt[i] & 1)
            start = i, flag++;
            if(flag > 2)
            {
                cout << "Impossible" << '\n';
                return 0;
            }
        }
        if(!start)
        {
            cout << "欧拉回路" << '\n';
            start = 1;
        }
        else
            cout << "欧拉路" << '\n';
        DFS(start);///从奇点开始搜
        for(int i = 1; i <= tot; ++i)
            cout << ans[i] << ' ';
        if(start != 1)
            cout << start << '\n';
    }
    return 0;
}