传送门

[前题提要]:自模板题以后,很少遇到欧拉回路的题目,正好这道题结合了多种经典算法,故写一篇题解记录一下

读完题面,因为需要经过所有1边,所以很显然会想到应该将所有的1边拿出来建一个新图,然后在新图上添加0边,使得新图是一个欧拉图.

让我们来回忆一下什么是欧拉图.对于无向图,其可以构造出欧拉回路的充要条件是所有点的度数都是偶数.

所以问题就变成了对于1图中度数为奇数的点,我们通过对其添加0边使得其的度数变为偶数.此时应该不难想到应该将那些度数为奇数的点拿出来考虑.并且应该会想到一个朴素的想法,我们给两个度数为奇数的点连一条边,他们不就同时变成偶数了吗.诶,此时应该还会诞生一个新的问题就是,如果两个度数为奇数的点之间不存在一条直连0边,那么我们该怎么办呢.我们如果找到一条路径是以这两个点为端点的0边路径,我们将其加入我们的1图中,会发生什么呢,我们会发现对于路径上的点我们这条路径并不会改变其奇偶性,而对于这两个点,我们改变了其奇偶性.那么问题就简单了,我们只要找到一些以上述点为端点的路径即可.但是此时又带来了一个新的问题,就是对于两条不同的需要加入的路径,他们可能存在一些边是重复的.肯定不能反复加入边.但是仔细想一想,我们之前加入一条路径是为了什么,是因为这样可以使我们中间点的度数奇偶性不改变,不然我们直接选两个要改变的点的直连边就行了,所以我们此时再想一下,对于重复边,如果他被选择的次数是偶数的话,那么我们不选择这条边,其点的奇偶性依旧没有变化.也就是对于覆盖次数为偶数的边,我们完全可以不选择加入该边,只对于覆盖次数为奇数的边我们才选择加入.附一张解释图:

对于(1,6),(5,7)来说,我们想改变他们,直接选择<1,2>,<2,5>,<4,6>,<4,7>即可.

所以的问题就变成了对于两个点,怎么找到一条连边.还要保证快速找到一条合法路径.注意到我们只需要找到任意一条路径即可.那么我们不难想到可以生成树.考虑对于0边所组成的图,我们对其进行生成树.那么我们最终会得到一个生成树森林.为什么是森林,因为原来的0边所组成的图并不一定是连通的.那么对于不同生成树之间是独立的,因为他们之间必然是不可能连边的.所以我们只要单独的去考虑每一棵生成树即可.那么不难会发现,对于一棵树,如果奇数度数节点的个数是奇数个,那么我们必然不可能完成目标,为什么这么说,因为我们不妨先每次选择两个没有被选择过的点,这样最后会剩下一个需要选择的点,此时我们会发现无论怎么选择,永远都会有一个点是奇数度数的节点,这个过程就和翻面(或者是点关灯)问题有点类似.反之,如果个数是偶数个,我们永远都可以直接选择两个没有被选过的点,然后加入以这两个点为端点的路径,使其满足条件

那么最后我们只需要跑一下欧拉回路的板子即可.对于如何求出一个合法欧拉图的欧拉回路,此处就不在赘述了.

---

下面是具体的代码部分:

 //It is guaranteed that you can reach any house from any other by walking on the roads with NPCs only.
//品了好久才明白,原来这句话保证了只保留1边依旧是一个联通图,又需要走全部1边,所以最终的欧拉回路是包括n个点的
//我本来还以为只是保证所有1边相连是一个联通图(也就是有些点的联通块全是0边).....
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls (rt<<1)
#define rs (rt<<1|1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define pd __gnu_pbds
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
inline void print(__int128 x){if(x<0) {putchar('-');x=-x;}if(x>9) print(x/10);putchar(x%10+'0');
}
#define maxn 1000010
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
vector<int>edge0[maxn];vector<pair<int,int> >edge1;
int in[maxn];int fa[maxn];
vector<int>tree[maxn];
vector<int>node[maxn];
int find(int x) {if(fa[x]==x) return x;else return fa[x]=find(fa[x]);
}int FA[maxn],max_son[maxn],Size[maxn],dep[maxn];
void dfs1(int u,int per_u) {Size[u]=1;for(int i=0;i<tree[u].size();i++) {int v=tree[u][i];if(v==per_u) continue;dep[v]=dep[u]+1;dfs1(v,u);FA[v]=u;Size[u]+=Size[v];if(Size[v]>Size[max_son[u]]) {max_son[u]=v;}}
}
int top[maxn];
void dfs2(int u,int t) {top[u]=t;if(!max_son[u]) return ;dfs2(max_son[u],t);for(int i=0;i<tree[u].size();i++) {int v=tree[u][i];if(v==FA[u]||v==max_son[u]) continue;dfs2(v,v);}
}
int LCA(int u,int v) {while(top[u]!=top[v]) {if(dep[top[u]]<dep[top[v]]) swap(u,v);u=FA[top[u]];}if(dep[u]>dep[v]) swap(u,v);return u;
}
int sum[maxn];
void dfs(int u,int pre_u) {for(auto v:tree[u]) {if(v==pre_u) continue;dfs(v,u);sum[u]+=sum[v];if(sum[v]&1) {edge1.push_back({u,v});}}
}vector<pair<int,int> >ng[maxn];
vector<int>path;
bool used[maxn];
void dfs_euler(int u){while(!ng[u].empty()){auto [j,id]=ng[u].back();ng[u].pop_back();if(used[id]) continue;used[id]=true;dfs_euler(j);}path.push_back(u);
}int main() {int T=read();while(T--) {int n=read();int m=read();for(int i=1;i<=m;i++) {int u=read();int v=read();int c=read();if(c) {edge1.push_back({u,v});in[u]++;in[v]++;}else {edge0[u].push_back(v);edge0[v].push_back(u);}}vector<int>v;for(int i=1;i<=n;i++) {if(in[i]&1) {v.push_back(i);}}for(int i=1;i<=n;i++) {fa[i]=i;}for(int i=1;i<=n;i++) {for(auto v:edge0[i]) {if(find(i)==find(v)) {continue;}fa[find(i)]=find(v);tree[i].push_back(v);tree[v].push_back(i);}}vector<int>ID;for(int i=1;i<=n;i++) {node[find(i)].push_back(i);if(find(i)==i) {ID.push_back(i);}}int flag=0;for(auto id:ID) {dfs1(id,0);dfs2(id,id);vector<int>temp;for(auto i:node[id]) {if(in[i]&1) {temp.push_back(i);}}if(temp.size()&1) {flag=1;break;}for(int i=1;i<temp.size();i+=2) {sum[temp[i-1]]++;sum[temp[i]]++;sum[LCA(temp[i-1],temp[i])]-=2;}dfs(id,0);}if(flag) {printf("NO\n");}else {printf("YES\n");int st=-1;for(int i=0;i<edge1.size();i++) {auto [a,b]=edge1[i];if(st==-1) st=a;ng[a].push_back({b,i});ng[b].push_back({a,i});}dfs_euler(st);printf("%d\n",path.size()-1);reverse(path.begin(),path.end());for(auto i:path) {printf("%d ",i);}printf("\n");	}//clearedge1.clear();path.clear();for(int i=0;i<=n;i++) {edge0[i].clear();node[i].clear();tree[i].clear();in[i]=fa[i]=FA[i]=max_son[i]=Size[i]=dep[i]=0;ng[i].clear();sum[i]=0;top[i]=0;}for(int i=0;i<=m;i++) {used[i]=0;}}return 0;
}