图论、欧拉路径

赛时认为音调和音高是两条可选的边，然后建不出图，对欧拉路径的认识非常肤浅刻薄。

进行欧拉路大学习！

首先发现所有音符使用一次这个条件与欧拉路径能解决的一笔画问题类似。

考虑到欧拉路是将所有边走过恰好一次，把音符刻画为边，由于方向不定，刻画为无向边，连接其对应的音高和音量。

发现构造出一个二分图，从一条边经过一个节点再到另一条边对应两个音符利用音高或音调拼接，这里音高或音调对应的是节点，而由于二分图的性质，路径上的节点在左右两部点中交替出现，对应着题目中交替利用音高和音调拼接的约束。

使用并查集判断图的连通性，使用 Hierholzer 算法找到欧拉路径。

总体时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
int n,m,f[400'005],du[400'005],hc[400'005];
vector<pair<int,int>> v[400'005];
bool on[200'005];
vector<int> ans;
int ask(int x){return x==f[x] ? x:f[x]=ask(f[x]);}
void dfs(int x,int edge){
    int lim=static_cast<int>(v[x].size())-1;
    for(int i=hc[x];i<=lim;i=hc[x]){
        ++hc[x];
        if(on[v[x][i].second]) continue;
        on[v[x][i].second]=1;
        dfs(v[x][i].first,v[x][i].second);
    }
    if(edge!=0) ans.push_back(edge);
}
void solution(){
    cin>>m,n=0,ans.clear();
    for(int i=1;i<=m;i++) on[i]=0;
    for(int i=1;i<=m*2;i++) f[i]=i,du[i]=0,hc[i]=0,v[i].clear();
    map<int,int> l,r;
    for(int i=1;i<=m;i++){
        static int x,y;
        cin>>x>>y;
        if(l[x]==0) l[x]=++n;
        if(r[y]==0) r[y]=++n;
        x=l[x],y=r[y],++du[x],++du[y];
        f[ask(x)]=ask(y);
        v[x].push_back({y,i});
        v[y].push_back({x,i});
    }
    int poi=0;
    for(int i=1;i<=n;i++) if(du[i]!=0) poi=i;
    for(int i=1;i<=n;i++) if(du[i]!=0&&ask(i)!=ask(poi)) return cout<<"No"<<'\n',void();
    int S=0,T=0;
    for(int i=1;i<=n;i++) if(du[i]&1){
        if(S==0) S=i;
        else if(T==0) T=i;
        else return cout<<"No"<<'\n',void();
    }
    if(S!=0&&T==0) return cout<<"No"<<'\n',void();
    if(S!=0) dfs(S,0);
    else dfs(poi,0);
    reverse(ans.begin(),ans.end());
    cout<<"Yes"<<'\n';
    for(int i:ans) cout<<i<<' ';
    cout<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}