花30分钟发现lg翻译出错了
又花30分钟学习欧拉回路怎么求
再花30分钟等待codeforces的queue
#include<bits/stdc++.h>
using namespace std;
int t,n,m;
vector<int> res;
struct edge{
int v,w,nx;
}e[1000005];
int cnt,hd[500005],deg[500005],sum[500005];
void add(int u,int v,int w){
e[++cnt]=edge{v,w,hd[u]};
hd[u]=cnt;
}
bool vis[500005];
void dfs(int u){
vis[u]=1;
for(int i=hd[u];i;i=e[i].nx){
int v=e[i].v;
if(vis[v] || e[i].w!=0)continue;
dfs(v);
if(deg[v]&1)deg[v]--,deg[u]--,e[i].w=e[i^1].w=-1;
}
}
stack<int> st;
void dfs2(int u){
st.push(u);
for(int i=hd[u];i;i=e[i].nx){
int v=e[i].v;if(e[i].w==-1)continue;
hd[u]=i;
e[i].w=e[i^1].w=-1;
dfs2(v);
break;
}
}
void work(){
st.push(1);
while(!st.empty()){
int u=st.top();st.pop();
int v=0;
for(int i=hd[u];i;i=e[i].nx){
if(e[i].w==-1)continue;
hd[u]=i;
v=e[i].v;break;
}
if(v)dfs2(u);
else{
for(int i=0;i<=sum[u];i++)res.emplace_back(u);
sum[u]=0;
}
}
}
void init(){
cnt=1;
for(int i=1;i<=n;i++)hd[i]=0,deg[i]=0,vis[i]=0,sum[i]=0;
res.clear();
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
init();
for(int i=1;i<=m;i++){
int u,v,w;scanf("%d%d%d",&u,&v,&w);
if(u==v){
if(w==1)sum[u]++;
continue;
}
add(u,v,w);add(v,u,w);
deg[u]++;deg[v]++;
}
bool flag=0;
for(int i=1;i<=n;i++)
if(!vis[i]){
dfs(i);
if(deg[i]&1)flag=1;
}
if(flag){
puts("NO");
continue;
}
work();
printf("YES\n%d\n",res.size()-1);
for(int i:res)printf("%d ",i);puts("");
}
return 0;
}
标签:int,每日,CF1994F,st,nx,一题,500005,void,hd
From: https://www.cnblogs.com/kentsbk/p/18331795