John's Trip

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2867 字
无向欧拉回路 Hierholzer
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1531
// 题意：多组无向图，每组给若干条街道（x,y,z，z 为街道编号），求从首条边两顶点中较小者出发、每条街道恰走一次的回路，输出街道编号序列（空格分隔、行末无空格）；不存在则输出 Round trip does not exist.
// 思路：无向图欧拉回路。先判所有有度数顶点度数均为偶数且连通；再跑 Hierholzer，取边时按街道编号升序（与样例一致），记录所用街道编号，逆序即正序。
// 复杂度：O(E log E) 时间 / O(V+E) 空间
// 易错点：自环也占度数且必须用到；输出街道编号而非顶点；不存在时整句照抄含句点；多组各输出一行。
#include <bits/stdc++.h>
using namespace std;
int main(){
    while(true){
        vector<pair<int,int>> edges;
        vector<int> zs;
        int startv = -1;
        bool any = false;
        while(true){
            int x, y;
            if(!(cin>>x>>y)) return 0;
            if(x==0 && y==0) break;
            any = true;
            if(startv==-1) startv = min(x,y);
            int z;
            cin>>z;
            edges.push_back({x,y});
            zs.push_back(z);
        }
        if(!any) break;
        int M = edges.size();
        map<int,int> deg;
        for(int i=0;i<M;i++){ deg[edges[i].first]++; deg[edges[i].second]++; }
        bool ok = true;
        for(auto& kv: deg) if(kv.second%2!=0) ok=false;
        if(ok){
            map<int,int> fa;
            for(auto& kv: deg) fa[kv.first]=kv.first;
            function<int(int)> find=[&](int x){return fa[x]==x?x:fa[x]=find(fa[x]);};
            for(int i=0;i<M;i++){
                int a=find(edges[i].first), b=find(edges[i].second);
                if(a!=b) fa[a]=b;
            }
            int root=-1;
            for(auto& kv: deg){
                int r=find(kv.first);
                if(root==-1) root=r;
                else if(root!=r) ok=false;
            }
        }
        if(!ok){
            cout<<"Round trip does not exist.\n";
            continue;
        }
        map<int,vector<int>> adj;
        for(int i=0;i<M;i++){
            adj[edges[i].first].push_back(i);
            adj[edges[i].second].push_back(i);
        }
        for(auto& kv: adj) sort(kv.second.begin(), kv.second.end(), [&](int a,int b){return zs[a]<zs[b];});
        map<int,vector<int>> pos;
        for(auto& kv: adj) for(int i=0;i<(int)kv.second.size();i++) pos[kv.first].push_back(i);
        vector<bool> used(M,false);
        vector<int> circuit;
        function<void(int)> dfs=[&](int v){
            while(true){
                int e=-1;
                for(int i=0;i<(int)adj[v].size();i++){
                    int idx=adj[v][i];
                    if(!used[idx]){ e=idx; break; }
                }
                if(e==-1) break;
                used[e]=true;
                int u=(edges[e].first==v)?edges[e].second:edges[e].first;
                dfs(u);
                circuit.push_back(zs[e]);
            }
        };
        dfs(startv);
        reverse(circuit.begin(), circuit.end());
        for(int i=0;i<(int)circuit.size();i++){
            if(i) cout<<' ';
            cout<<circuit[i];
        }
        cout<<"\n";
    }
    return 0;
}
John's Trip

正文

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