AcWing 1184. 欧拉回路

题目传送门

一、前导知识

1、对于无向图，所有边都是连通的。

• 存在欧拉路径的充分必要条件：度数为奇数的点只能有\(0\)或\(2\)个。
• 存在欧拉回路的充分必要条件：度数为奇数的点只能有\(0\)个。

2、对于有向图，所有边都是连通。

• 存在欧拉路径的充分必要条件：要么所有点的出度均等于入度；要么除了两个点之外，其余所有点的出度等于入度，剩余的两个点：一个满足出度比入度多\(1\)（起点），另一个满足入度比出度多\(1\)（终点）
• 存在欧拉回路的充分必要条件：所有点的出度均等于入度。

二、遍历过程中的注意事项

三、边的转化

无向图中的边的序号为:\(0~2m-1\),而在题目中的编号是\(1~m\);
所以转化边时:\(0\),\(1\)对应\(1\)号边,\(2\),\(3\)对应\(2\)号边,即\(x\)号边对应\(x/2+1\)
其中偶数是正向边,奇数是反向边,可以用x^1转化正反向边的关系;
如果是奇数:x^1中,\(x\)二进制前面的数不变,最后一位变成\(0\),即x^1=x-1;
如果是偶数:x^1中,\(x\)二进制前面的数不变,最后一位变成\(1\),即x^1=x+1;

四、实现代码

#include 
using namespace std;
const int N = 100010, M = 400010;
int t;               // 类型 1:无向边  2:有向边
int n, m;            // 点和边的数量
int din[N], dout[N]; // 分别表示入度和出度
//邻接表
int e[M], h[N], idx, ne[M];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool st[M];
vector path; //欧拉路径

// 背过，为了防止自环，代码稍难理解一些
// 无向图 求欧拉回路
void dfs1(int u) {
    // 遍历这个点的所有临点，查重，删除边，dfs，加点
    while (~h[u]) { // h[u] 表示当前可用的第一条边
        // 无向图需要额外查重
        if (st[h[u]]) {
            h[u] = ne[h[u]];
            continue;
        }
        st[h[u]] = st[h[u] ^ 1] = true;
        // 保留当前边后，删边!
        int i = h[u];
        h[u] = ne[i]; // 删边
        // dfs
        dfs1(e[i]);
        // 加边
        int t = i / 2 + 1;
        if (i & 1) t *= -1; //反向边，输出负号
        path.push_back(t);
    }
}
// 有向图求欧拉回路
void dfs2(int u) {
    while (~h[u]) { // h[u] 表示当前可用的第一条边
        // 保留当前边后，删边!
        int i = h[u]; // i边号
        h[u] = ne[i]; // 删边
        // dfs
        dfs2(e[i]); // e[i]点号
        // 加边
        path.push_back(i + 1); //下标从0开始，点的编号从1到n
    }
}

int main() {
    memset(h, -1, sizeof h);
    cin >> t >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        if (t == 1) add(b, a);
        din[b]++, dout[a]++;
    }
    // 是否满足 无向图/有向图 各自的性质
    if (t == 1) { // 无向图 所有点的度都为偶数
        for (int i = 1; i <= n; i++)
            if (din[i] + dout[i] & 1) {
                puts("NO");
                return 0;
            }
    } else { // 有向图 所有点的入度==出度
        for (int i = 1; i <= n; i++)
            if (din[i] != dout[i]) {
                puts("NO");
                return 0;
            }
    }
    // 是否满足 连通性  需要找一个非孤立点作为起始点
    for (int i = 1; i <= n; i++)
        if (~h[i]) { // h[i]==-1表示没有邻接边，孤立的点
            if (t == 1)
                dfs1(i); // 无向边
            else
                dfs2(i); //有向边
            break;       //这个break很关键，没有的话，后面cnt= 0; i--) printf("%d ", path[i]);
    return 0;
}