UOJ 117 欧拉回路(输出路径)

Description

一张无向图(或有向图),找出(若能找出)欧拉回路并输出路径。可能有重边、自环。

题目链接：http://uoj.ac/problem/117

Code 代码赏析

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define eps 1e-8
#define PI acos(-1.0)
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
#define Close ios::sync_with_stdio(false);
#define Debug cout << "-----------------" << '\n';
const int N = 200010;


int n, m, cnt, num_max;
int ecnt = 1, head[N], pre[N * 2], to[N * 2];///链式前向星
int in[N], out[N];
int top, ans[N * 2];
bool vis[N * 2];

void add(int u, int v)
{
    ecnt++;
    pre[ecnt] = head[u];
    head[u] = ecnt;
    to[ecnt] = v;
}

void DFS(int now, bool flag)
{
    for(int & e = head[now]; e; e = pre[e])
    {
        if(vis[e])
            continue;
        cnt++;
        vis[e] = 1;
        if(flag)
            vis[e ^ 1] = 1;
        int t = e;
        DFS(to[e], flag);
        ans[++top] = t;
    }
}


int main()
{
    int t, u, v;
    scanf("%d", &t);
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++i)
    {
        scanf("%d%d", &u, &v);
        add(u, v);
        in[v]++, out[u]++;
        if(t == 1)
            add(v, u), in[u]++, out[v]++;
        num_max = max(num_max, max(u, v));
    }
    if(t == 1)
    {
        for(int i = 1; i <= num_max; ++i)
            if(in[i] & 1)
            {
                puts("NO");
                return 0;
            }
    }
    if(t == 2)
    {
        for(int i = 1; i <= num_max; ++i)
            if(in[i] != out[i])
                {
                    puts("NO");
                    return 0;
                }
    }
    if(t == 1)
        DFS(num_max, 1);
    else
        DFS(num_max, 0);
    if(cnt == m)
    {
        puts("YES");
        for(int i = top; i >= 1; --i)
        {
            if(t == 2)
                cout << ans[i] - 1 << ' ';
            else
            {
                if(ans[i] & 1)
                    putchar('-');
                cout << ans[i] / 2 << ' ';
            }
        }
    }
    else
        puts("NO");
    return 0;
}

Explain

从main()函数开始解释：

(非结构体)链式前向星添加边:

未参与排序的结构体是没有灵魂的(slow)，数组完全可以代替

ecnt计数(边数)：从2开始计数？

原因①：vis[e] 、vis[e ^ 1]这种方法规定边从偶数(0/2/4/etc)开始存

原因②：链式前向星遍历时以-1结束，此处不愿memset(-1)，便是以0结束，所以e == 0被占用作为循环结束标志，0不可用只能从2开始计数

添边的同时统计入度与出度：

对于存在欧拉回路的无向图：入度(==出度)不存在奇数

对于存在欧拉回路的有向图：每个点的入度必须等于出度

添边的同时记录出现过的最大的结点标号(num_max)？

题目给出数字n，代表有n个点，但不一定所有点都会被提及，所以num_max可以作为DFS入口。另外，测试每个点入度与出度是否合理的时候，num_max可以做遍历上限，省去不必要的遍历

DFS套圈法(cnt计数判连通)：

这里用了引用(&)，通过改变head数组的值实现“边的删除”以保证O(E)的复杂度

用题解中的一句话来说：对于访问过的边不能直接打标记跳过(如果一直给自环那么dfs循环边就是n方)，但还是要标记的

输出答案：

对于有向图，输出边的编号减一，因为我们的边是从2开始存的，题目从1开始

对于无向图，若边的标号为偶数，便是题目所给的u到v的走法，若为奇数，则是我们添的从v到u的辅助边走法。因为题目给的一条边我们对应填了两条，所以要 / 2

受 https://blog.csdn.net/qq_35649707/article/details/75578102 启发