欧拉回路

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2555 字
第一行t表示子任务，t=1处理无向图、t=2
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1527
// 题意：第一行 t 表示子任务，t = 1 处理无向图、t = 2 处理有向图，接下来给 n 个点 m 条边（可重边可自环），能一笔画就输出 YES 和 m 条边的经过顺序（无向图用负数表示反着走），否则输出 NO。
// 思路：先判度数条件（无向图所有点度为偶，有向图每点入度等于出度），再用 Hierholzer 算法跑一条欧拉回路，最后看取出的边数是否等于 m 来确认图连通。
// 1. 用栈做非递归 Hierholzer：一直沿着没走过的边往前走，走不动了就把它进栈时经过的那条边倒序记下来，最后整体翻转。
// 2. 无向图一条边拆成两个方向的有向弧，弧上带符号，顺着走记正、逆着走记负，走过一次就把整条边标记掉。
// 复杂度：O(n + m) 时间 / O(n + m) 空间
// 易错点：度数条件满足但图不连通时依然无解，必须用「最后取出的边数等于 m」再判一次，只看度数会漏掉这种情况。
// 易错点：无向图记录的是带符号的边号，两条弧要用同一个编号标记已访问，只标记一条会导致同一条边被走两次。
#include <bits/stdc++.h>
using namespace std;
struct Arc{
    int to;
    int id;
    int sign;
};
int main(){
    int t;
    if(!(cin >> t)) return 0;
    int n, m;
    cin >> n >> m;
    vector<vector<Arc> > g(n + 1);
    vector<int> deg(n + 1, 0), ind(n + 1, 0), outd(n + 1, 0);
    for(int i = 1; i <= m; i++){
        int v, u;
        cin >> v >> u;
        Arc a;
        a.to = u;
        a.id = i;
        a.sign = 1;
        g[v].push_back(a);
        if(t == 1){
            Arc b;
            b.to = v;
            b.id = i;
            b.sign = -1;
            g[u].push_back(b);
            deg[v]++;
            deg[u]++;
        }else{
            outd[v]++;
            ind[u]++;
        }
    }
    bool ok = true;
    for(int i = 1; i <= n; i++){
        if(t == 1){
            if(deg[i] % 2 != 0) ok = false;
        }else{
            if(ind[i] != outd[i]) ok = false;
        }
    }
    if(!ok){
        cout << "NO" << "\n";
        return 0;
    }
    int s = 0;
    for(int i = 1; i <= n; i++){
        if(!g[i].empty()){
            s = i;
            break;
        }
    }
    vector<int> ptr(n + 1, 0);
    vector<char> used(m + 1, 0);
    vector<int> st, ste, seq;
    if(s > 0){
        st.push_back(s);
        ste.push_back(0);
        while(!st.empty()){
            int u = st.back();
            while(ptr[u] < (int)g[u].size() && used[g[u][ptr[u]].id]) ptr[u]++;
            if(ptr[u] == (int)g[u].size()){
                if(ste.back() != 0) seq.push_back(ste.back());
                st.pop_back();
                ste.pop_back();
                continue;
            }
            Arc a = g[u][ptr[u]];
            ptr[u]++;
            used[a.id] = 1;
            st.push_back(a.to);
            ste.push_back(a.sign * a.id);
        }
    }
    if((int)seq.size() != m){
        cout << "NO" << "\n";
        return 0;
    }
    reverse(seq.begin(), seq.end());
    cout << "YES" << "\n";
    for(int i = 0; i < m; i++){
        if(i) cout << " ";
        cout << seq[i];
    }
    cout << "\n";
    return 0;
}
欧拉回路

正文

一本通·提高篇的其它内容
