Codeforces Round 1026 (Div. 2)-CF-1026-E. Melody

题目大意

https://codeforces.com/contest/2110/problem/E

题目描述
给定 $n$ 个不同的声音，每个声音由音量 $v_i$ 和音高 $p_i$ 两个属性组成。
你需要将这 $n$ 个声音排列成一个序列，每个声音恰好出现一次。
一个合法的序列需要同时满足以下两个条件：

1. 任意两个相邻的声音，必须且仅有一个属性相同（即要么音量相同且音高不同，要么音高相同且音量不同）。

2. 任意连续的三个声音，它们的音量不能完全相同，音高也不能完全相同（即不能出现连续三个声音音量一样，也不能出现连续三个声音音高一样）。

请判断是否存在这样的合法序列。如果存在，输出 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（按值进行图论建模）（欧拉回路）

注意，欧拉路径存在的充要条件（在无向连通图上），就是奇数度数节点数量等于0 或者 2。说白了，就是相比于回路，我们允许你的这个起点和终点搞点怪，只进不出或者只出不进，但是我们不允许你的其他点违反这一法则。

这两道题目应该是比较类似的。

在算法竞赛中，采用排除法还是一个比较好的办法。这道题目其实还是一样的，其他方法不太适合解决这种问题，那么只能够求助于图论建模了。

我们想问怎么样建这张图，实际上这个题目是rearrangement问题，它只有一个可以连边的东西，对吧，那就是V和P之间去连，V和P之间按值连接。这也是使用排除法，因为其他东西你都不知道，它怎么排，你怎么去连，对吧。

然后我们还是一样的套路，就是一开始是一张无向图，然后通过遍历进行定向。然后我们怎么样进行这个呢？这个遍历需要遵循怎样的规则呢？我个人认为呢，这个遍历所需要遵循的规则就是，首先它不能够去访问父节点（会造成连续的两个声音音量和音高重合），然后每条边仅遍历一次。

DFS 式探路（失败）

要这样子搞的话，我们有一个疑问啊，就是能不能满足题目上要求的任意连续的三个声音，它们的音量不能完全相同，音高也不能完全相同，就是这个特性能不能满足呢？我们实际写出来的程序无法通过样例，你看唯一输出no的样例，就是我们下面画的这个东西。那么我们程序呢，它就是因为我们程序采用的是DFS递归式的实现，那么它访问了2以后，它会继续访问3，那么实际上这边是，共用了一撇，所以说的话会出现一些问题，那我们就是要给这个DFS函数加一个这个长度的这个返回值就行了。至少目前是这么打算，这样子尝试一下。

那么我们发现呢，采用DFS递归式的这个实现还会有一个问题，就是他好像走的有点问题，因为它虽然岸边连接，但不是一个完整的回路，所以可能像树一样，我们是一个线性结构。像树一样的话，最后是断开来的，就是会导致这个 pitch 和 voice没有一个是相等的。

DFS写的话，这个递归它不符合这个线性特征，所以说的话不太适合。我们决定采用类似于CF 1081e的做法，但有一个问题，CF 1081e可以确保所有点的入度和出度。如果这张图是一张无像图，认为所有点的度数都是偶数，可以保证这一点，因为不保证这一点的图就是错的，输出no就可以了。但这道题不一定，如果作无像图，每个点的度数不一定是偶数，只是偶数时才有解，它可以不是偶数这也是可以的。

不过我们上面也说了，通过对欧拉路径的学习，我们知道：

奇数度数节点数量等于 0 或者 2。

注意还有判断图是否联通，这个也是非常重要的。

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

源代码

/**
 * 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

starsilk 的代码

#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的起点是非常重要的。在欧拉路径当中，欧拉回路我们当然是无所谓，但是欧拉路径的这个起始位置是要注意的。

我们采用的策略是有奇数点就选奇数点，没有奇数点就选随便选一个点。