罪人挽歌 题解
简化题意：
给定 \(n\) 个二元组，第 \(i\) 个二元组的值为 \((a, b)\)，保证任意两个二元组都不相同。
求是否存在一个二元组的排列，使得这些二元组满足对于任意 \(1 \leq i < n\)，有 \(A_i = A_{i+1}\) 或 \(B_i = B_{i+1}\)，且对于任意 \(2 \leq i < n\)，\(A_{i-1} = A_i = A{i+1}\) 和 \(B_{i-1} = B_i = B_{i+1}\) 都不成立。如果有解，还需找到字典序最小的解。
思路：
首先我们可以列出一个合法的方案，如下：
a b
c b
c e
a e
...
我们把相同的字母连起来，发现了没？是不是很像欧拉路！
我们可以把 \(a\) 与 \(b\) 连边（当然 \(b\) 必须加上 \(n\) 来区分左右部点），这样就形成了一个二分图。
那么，一个序列有解，当且仅当去掉所有大小为 \(1\) 的连通块后，仅剩下一个连通块，且存在一条欧拉路径。答案就是字典序最小的欧拉路径。
我们来证明一下这样做的正确性。必要性很显然，因为如果存在一个解，那么将上下相同的点连起来，形成的就是一条欧拉回路。
至于充分性，考虑反证。假设一条欧拉路径无解，则形成的序列必然为以下形式：
a b
c b
c b
而题目保证任意两个二元组都不相同，因此假设错误，原命题成立。
至于保证字典序最小，我们贪心的选编号更小的边来跑欧拉路即可。这里可以利用邻接表存图是倒序的性质，倒着加边，这样第一个遍历的边就一定是编号最小的。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+100;
inline int read() {
int x = 0; char ch = getchar();
while(ch<'0' || ch>'9') ch = getchar();
while(ch>='0'&&ch<='9') x = x*10+(ch-48), ch = getchar();
return x;
}
//欧拉回路？
//不一定是回路。
//把出边按先后顺序排序一下（
//额……邻接表是倒着存的图，那就反着加边（
//并查集维护一下联通块
int head[N], tot = 1;
struct node{
int nxt, to, id;
}edge[N<<2];
void add(int u, int v, int id){
edge[++tot].nxt = head[u];
edge[tot].to = v;
edge[tot].id = id;
head[u] = tot;
}
int de[N];
vector<int> vc[N];
int totc;
int col[N];
int n;
struct DSU {
int fa[N];
void init() {
for(int i = 1; i<=n*2; ++i) fa[i] = i;
}
int find(int x) {
if(x != fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
void merge(int x, int y) {
x = find(x), y = find(y);
if(x == y) return;
fa[x] = y;
}
}dsu;
int a[N], b[N];
int vis[N];//记录每个点最早有边的时刻。
int visc[N];//记录每个连通块最早有边的时刻。
bool vise[N<<2];
int ans[N], tota;
int st, ed;
int edid = -1;
void dfs(int u, int from) {
// cout << de[ed] << endl;
for(int &i = head[u]; i; i = edge[i].nxt) {
if(vise[i]) continue;
vise[i] = vise[i ^ 1] = 1;
// ans[++tota] = edge[i].id;
// if(ans[tota] == 240) printf("%d\n", tota);
dfs(edge[i].to, edge[i].id);
}
ans[++tota] = from;
}
bool flag;
void work(int id) {
if(vc[id].size() == 1) return;
if(flag) {
puts("No");
exit(0);
}
flag = 1;
st = -1, ed = -1; int cnt = 0;
for(int i: vc[id]) {
if(de[i] & 1) {
if(st == -1){
st = i;
} else ed = i;
++cnt;
if(cnt > 2) {
puts("No");
exit(0);
}
}
}
if(cnt == 1) {
puts("No");
exit(0);
}
if(cnt == 2) {
if(vis[st] > vis[ed]) swap(st, ed);
dfs(st, 0);
} else{
ed = -1;
st = vc[id][0];
for(int i: vc[id]) {
if(vis[i] < vis[st]) {
st = i;
}
}
dfs(st, 0);
}
}
int q[N], top;
bool cmp(int x, int y) {
return visc[x] < visc[y];
}
int main() {
n = read();
dsu.init();
for(int i = 1; i<=n; ++i) {
a[i] = read(), b[i] = read() + n;
if(!vis[a[i]]) {
vis[a[i]] = i;
}
if(!vis[b[i]]) {
vis[b[i]] = i;
}
dsu.merge(a[i], b[i]);
}
for(int i = n; i>=1; --i) {
add(a[i], b[i], i);
add(b[i], a[i], i);
++de[a[i]], ++de[b[i]];
}
for(int i = 1; i<=n*2; ++i) {
int fi = dsu.find(i);
if(col[fi]) {
visc[col[fi]] = min(vis[i], visc[col[fi]]);
vc[col[fi]].push_back(i);
} else{
col[fi] = ++totc;
q[++top] = totc;
visc[totc] = vis[i];
vc[totc].push_back(i);
}
}
sort(q+1, q+top+1, cmp);
for(int T = 1; T<=top; ++T){
work(q[T]);
}
puts("Yes");
// if(tota < n) ans[++tota] = edid;
for(int i = 1, j = tota-1; i<=n; ++i, --j) {
if(i > 1) putchar(' ');
printf("%d", ans[j]);
}
putchar('\n');
return 0;
}