当前位置：首页 > article >正文

E. Melody 【CF1026 (Div. 2)】 (求欧拉路径之Hierholzer算法)

article 2025/8/24 22:59:12

E. Melody

思路

将所有出现过的音量和音高看作一个点，一个声音看作一条边，连接起来。那么很容易知道要找的就是图上的一条欧拉路径（类似一笔画问题）

又已知存在欧拉路径的充要条件为：度数为奇数的点的个数为0或者2个，可以先判断部分为NO的情况。

数据范围要求离散化存点，然后用Hierholzer算法找欧拉路径。算法思想很简单，dfs时把走过的边都删掉，如果一个点递归处理完毕就加入到队列中（这里是存边，也是同理，不过是递归后记录边的序号），最后队列里记录的是反向的路径顺序。

dfs的起点是度数为奇数的点（如果存在），这里利用的是当前弧优化+vis数组来处理删边，以及比较最后n与ans的大小来判断图是否联通。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int, int>
#define FU(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, a, b) for (int i = (a); i >= (b); --i)
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 5e5 + 5, MAXN = maxn;
int ne[maxn]; // 当前弧优化
vector<pii> G[maxn];
vector<int> ans;
bool vis[maxn];
void dfs(int x) {for (int i = ne[x]; i < G[x].size(); i = ne[x]) {ne[x] = i + 1;auto [y, eid] = G[x][i];if (vis[eid])continue;vis[eid] = true;dfs(y);ans.push_back(eid); // 递归后记录边}
}void solve() {ans.clear();int n;cin >> n;FU(i, 1, 2 * n) {G[i].clear();ne[i] = 0;vis[i] = 0;}map<int, int> mu, mv;int im = 0;FU(i, 1, n) {int u, v;cin >> u >> v;if (mu[u] == 0)mu[u] = ++im;if (mv[v] == 0)mv[v] = ++im;G[mu[u]].pb({mv[v], i}); // u -> {v,eid}G[mv[v]].pb({mu[u], i});}int cntj = 0;int qd = 1;FU(i, 1, im) {if (G[i].size() % 2 == 1)qd = i, cntj++;}if (cntj != 0 && cntj != 2) {cout << "NO\n";return;}dfs(qd);if (ans.size() != n) { // 说明不连通cout << "NO\n";return;}cout << "Yes\n";for (int e : ans) {cout << e << " ";}cout << endl;
}signed main() {
#ifdef ONLINE_JUDGE
#elsefreopen("../in.txt", "r", stdin);
#endifcin.tie(0)->ios::sync_with_stdio(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}