Codeforces Round 1026 (Div. 2)-CF-1026-E. Melody · znzryb
## 题目大意
[https://codeforces.com/contest/2110/problem/E](https://codeforces.com/contest/2110/problem/E)
**题目描述**
给定 $n$ 个不同的声音，每个声音由音量 $v_i$ 和音高 $p_i$ 两个属性组成。
你需要将这 $n$ 个声音排列成一个序列，每个声音恰好出现一次。
一个合法的序列需要同时满足以下两个条件：
1. 任意两个相邻的声音，必须且仅有一个属性相同（即要么音量相同且音高不同，要么音高相同且音量不同）。
1. 任意连续的三个声音，它们的音量不能完全相同，音高也不能完全相同（即不能出现连续三个声音音量一样，也不能出现连续三个声音音高一样）。
请判断是否存在这样的合法序列。如果存在，输出 `YES` 以及排列后各个声音的初始编号；如果不存在，输出 `NO`。
**输入格式**
第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示声音的数量。
接下来的 $n$ 行，每行包含两个整数 $v_i$ 和 $p_i$（$1 \le v_i, p_i \le 10^9$），分别表示第 $i$ 个声音的音量和音高。保证同一个测试用例中不会出现音量和音高都完全相同的两个声音。
所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。
**输出格式**
如果存在合法的序列，第一行输出 `YES`，第二行输出 $n$ 个整数，表示合法的声音排列顺序对应的原始编号（从 1 开始）。
如果不存在，输出 `NO`。`YES` 和 `NO` 忽略大小写。
**样例**
```
输入：
5
4
179 239
179 179
239 179
239 239
3
1 1
2 1
3 1
1
5 7
5
1 1
1 2
2 1
2 2
99 99
7
1 1
1 3
2 1
2 2
3 1
3 2
3 3
输出：
YES
4 3 2 1
NO
YES
1
NO
YES
3 4 6 7 2 1 5
```
**样例解释**
在第一个测试用例中，按照 4, 3, 2, 1 的顺序排列，声音序列为：$(239,239)-(239,179)-(179,179)-(179,239)$。包含了所有的声音，并且任意两个相邻的声音都仅有一个属性（音量或音高）不同，满足所有条件。
在第二个测试用例中，3 个声音的音高全部是 1，这意味着无论如何排列，都会出现连续三个声音音高相同的情况，因此无法构造合法的序列。
## 思路讲解
[Codeforces Round 1081 (Div. 2)-CF-1081-E. Swap to Rearrange（按值进行图论建模）（欧拉回路）](/2026/02/22/20260222-b6e20294)
注意，欧拉路径存在的充要条件（在无向连通图上），就是**奇数度数节点数量等于0 或者 2**。说白了，就是相比于回路，我们允许你的这个起点和终点搞点怪，只进不出或者只出不进，但是我们不允许你的其他点违反这一法则。
这两道题目应该是比较类似的。
在算法竞赛中，采用排除法还是一个比较好的办法。这道题目其实还是一样的，其他方法不太适合解决这种问题，那么只能够求助于图论建模了。
我们想问怎么样建这张图，实际上这个题目是rearrangement问题，它只有一个可以连边的东西，对吧，那就是V和P之间去连，V和P之间按值连接。这也是使用排除法，因为其他东西你都不知道，它怎么排，你怎么去连，对吧。
然后我们还是一样的套路，就是一开始是一张无向图，然后通过遍历进行定向。然后我们怎么样进行这个呢？这个遍历需要遵循怎样的规则呢？我个人认为呢，这个遍历所需要遵循的规则就是，首先它不能够去访问父节点（会造成连续的两个声音音量和音高重合），然后每条边仅遍历一次。
::: DFS 式探路（失败）
要这样子搞的话，我们有一个疑问啊，就是能不能满足题目上要求的任意连续的三个声音，它们的音量不能完全相同，音高也不能完全相同，就是这个特性能不能满足呢？我们实际写出来的程序无法通过样例，你看唯一输出no的样例，就是我们下面画的这个东西。那么我们程序呢，它就是因为我们程序采用的是DFS递归式的实现，那么它访问了2以后，它会继续访问3，那么实际上这边是，共用了一撇，所以说的话会出现一些问题，那我们就是要给这个DFS函数加一个这个长度的这个返回值就行了。至少目前是这么打算，这样子尝试一下。
那么我们发现呢，采用DFS递归式的这个实现还会有一个问题，就是他好像走的有点问题，因为它虽然岸边连接，但不是一个完整的回路，所以可能像树一样，我们是一个线性结构。像树一样的话，最后是断开来的，就是会导致这个 pitch 和 voice没有一个是相等的。
:::
DFS写的话，这个递归它不符合这个线性特征，所以说的话不太适合。我们决定采用类似于CF 1081e的做法，但有一个问题，CF 1081e可以确保所有点的入度和出度。如果这张图是一张无像图，认为所有点的度数都是偶数，可以保证这一点，因为不保证这一点的图就是错的，输出no就可以了。但这道题不一定，如果作无像图，每个点的度数不一定是偶数，只是偶数时才有解，它可以不是偶数这也是可以的。
不过我们上面也说了，通过对欧拉路径的学习，我们知道：
**奇数度数节点数量等于 0 或者 2**。
注意还有判断图是否联通，这个也是非常重要的。
```cpp
if (odd_cnt!=0 && odd_cnt!=2) {
cout<<"NO\n";
return;
}
vector<ll> ans_ls;
auto dfs=[&](auto && self,ll u) -> void {
while (!g[u].empty()) {
auto it=g[u].begin();
auto [to,id]=*it;
g[u].erase(it);
g[to].erase({u,id});
self(self,to);
ans_ls.push_back(id);
}
};
dfs(dfs,max(start_node,g.begin()->first));
// 判断图是否联通，如果不联通，也是错的。
if (SZ(ans_ls)!=N) {
cout<<"NO\n";
return;
}
reverse(all(ans_ls));
cout<<"YES\n";
for (auto u:ans_ls) {
cout<<u<<" ";
}
cout<<"\n";
```
为什么 Euler 路径红色这样子写有问题呢？其实也很容易理解，因为**我们要把 ans_ls 反过来的呀**！所以说，肯定需要先遍历完后续的点，才能塞入这条边啊！其实简单来说，就是**要和正常的反过来**！
还有我们要注意起点选择，就是DFS的起点是非常重要的。在欧拉路径当中，欧拉回路我们当然是无所谓，但是欧拉路径的这个起始位置是要注意的。
我们采用的策略是有奇数点就选奇数点，没有奇数点就选随便选一个点。
## AC代码
AC
[https://codeforces.com/contest/2110/submission/364850915](https://codeforces.com/contest/2110/submission/364850915)
::: 源代码
```cpp
/**
* Problem: E. Melody
* Contest: Codeforces Round 1026 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2110/problem/E
* Created: 2026-02-28 21:10:58
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
struct To_id{
ll to,id;
auto operator<=>(const To_id&) const=default;
};
void Solve() {
ll N;
cin >> N;
map<ll,set<To_id>> g;
for (int i=1;i<=N;++i) {
ll u,v;
cin>>u>>v;
v+=1e9;
g[u].insert({v,i});
g[v].insert({u,i});
}
ll odd_cnt=0;
ll start_node=0;
for (auto &[u,vec]:g) {
if (SZ(vec)&1) {
start_node=u;
odd_cnt++;
}
}
if (odd_cnt!=0 && odd_cnt!=2) {
cout<<"NO\n";
return;
}
vector<ll> ans_ls;
auto dfs=[&](auto && self,ll u) -> void {
while (!g[u].empty()) {
auto it=g[u].begin();
auto [to,id]=*it;
g[u].erase(it);
g[to].erase({u,id});
self(self,to);
ans_ls.push_back(id);
}
};
dfs(dfs,max(start_node,g.begin()->first));
if (SZ(ans_ls)!=N) {
cout<<"NO\n";
return;
}
reverse(all(ans_ls));
cout<<"YES\n";
for (auto u:ans_ls) {
cout<<u<<" ";
}
cout<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2110/submission/364850915
1
5
1 1
1 2
2 1
2 2
99 99
*/
```
:::
[https://codeforces.com/contest/2110/submission/321091518](https://codeforces.com/contest/2110/submission/321091518)
::: starsilk 的代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int x[200000],y[200000];
map<int,int>mpx,mpy;
struct linex{
int v;
int id;
};
vector<linex>line[400000];
int deg[400000],curp[400000],visl[200000];
vector<int>ansv;
void dfs(int t){
int tv,tid;
while(curp[t]<line[t].size())
{
tv=line[t][curp[t]].v;
tid=line[t][curp[t]].id;
curp[t]++;
if(visl[tid])continue;
visl[tid]=1;
dfs(tv);
ansv.push_back(tid);
}
}
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int T,n,i,cx,cy,cnt,p;
linex lx;
for(cin>>T;T>0;T--)
{
cin>>n;
cx=0;
cy=0;
for(i=0;i<n;i++)
{
cin>>x[i]>>y[i];
if(mpx.find(x[i])==mpx.end())
{
mpx[x[i]]=cx;
cx++;
}
x[i]=mpx[x[i]];
if(mpy.find(y[i])==mpy.end())
{
mpy[y[i]]=cy;
cy++;
}
y[i]=mpy[y[i]];
visl[i]=0;
}
mpx.clear();
mpy.clear();
for(i=0;i<cx+cy;i++)
{
deg[i]=0;
curp[i]=0;
}
for(i=0;i<n;i++)
{
lx.v=y[i]+cx;
lx.id=i;
line[x[i]].push_back(lx);
lx.v=x[i];
lx.id=i;
line[y[i]+cx].push_back(lx);
deg[x[i]]++;
deg[y[i]+cx]++;
}
cnt=0;
p=0;
for(i=0;i<cx+cy;i++)
{
if(deg[i]&1)
{
cnt++;
p=i;
}
}
if(cnt>2)
{
cout<<"NO\n";
for(i=0;i<cx+cy;i++)line[i].clear();
continue;
}
dfs(p);
if(ansv.size()!=n)
{
cout<<"NO\n";
for(i=0;i<cx+cy;i++)line[i].clear();
ansv.clear();
continue;
}
cout<<"YES\n";
for(i=0;i<ansv.size();i++)cout<<ansv[i]+1<<' ';
cout<<'\n';
ansv.clear();
for(i=0;i<cx+cy;i++)line[i].clear();
}
return 0;
}
```
:::
## 心路历程（WA，TLE，MLE……）
为什么 Euler 路径红色这样子写有问题呢？其实也很容易理解，因为**我们要把 ans_ls 反过来的呀**！所以说，肯定需要先遍历完后续的点，才能塞入这条边啊！其实简单来说，就是**要和正常的反过来**！
还有我们要注意起点选择，就是DFS的起点是非常重要的。在欧拉路径当中，欧拉回路我们当然是无所谓，但是欧拉路径的这个起始位置是要注意的。
我们采用的策略是有奇数点就选奇数点，没有奇数点就选随便选一个点。
