BUPT2017 wintertraining(15) #7A
题意
给你一个图，n个点m条边，求走遍所有边，至少经过几次点，及输出依次经过的点。n and m (2 ≤ n ≤ 10^5, 1 ≤ m ≤ 2·10^5)
样例
Input 9 5 2 4 2 6 3 5 3 9 5 9 Output 7 3 9 5 3 6 2 4 Input 4 5 1 2 1 3 1 4 2 4 3 4 Output 6 4 3 1 4 2 1
题解
首先依次从度数为奇数的点出发，走完所有的链。接着把和链相连的环走完，走环的时候用的是走欧拉路径（这里算是欧拉回路）的方法。再把剩下的环走完。 重点是，需要模拟一个链表来连接链和链上的环。
代码
代码语言：javascript复制#include <cstdio>
#define N 100005
#define M 400005
using namespace std;
int n,m;
struct edge{
int to,next;
bool vis;
}e[M];
int head[N],cnt=2;
int du[N];//点的度数
int idx[N];//点在s中的序号
int ans,sub;//sub是可以减去的步数
int s[M];//存储答案链表
int nxt[M];//nxt[i]代表s[i]在链表中的下一个
void add(int u,int v){
du[u];
e[cnt]=(edge){v,head[u]};
head[u]=cnt ;
}
void dfs(int x){
nxt[ans]=ans 1;
s[ ans]=x;
idx[x]=ans;
for(int &i=head[x];i;i=e[i].next){
if(e[i].vis)continue;
e[i].vis=e[i^1].vis=true;
--du[x],--du[e[i].to];
dfs(e[i].to);
break;//每次只找出一条连续的链
}
}
//找出欧拉回路
void dfs2(int x){
for(int &i=head[x];i;i=e[i].next){
if(e[i].vis)continue;
e[i].vis=e[i^1].vis=true;
--du[x],--du[e[i].to];
dfs2(e[i].to);
}
nxt[ans]=ans 1;
s[ ans]=x;
}
int main() {
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m; i){
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
for(int i=1;i<=n; i)
if(du[i]&1)dfs(i);//走完所有的链
#ifdef _LOCAL
for(int i=1;i<=ans; i)printf("%d ",s[i]);
puts("");
#endif
for(int i=1;i<=n; i)
if(idx[i]&&du[i]){//把链上连着的环走完
int t=ans;
dfs2(i);
nxt[idx[i]]=t 2;
nxt[ans]=idx[i] 1;
nxt[t]=0;
sub;
}
for(int i=1;i<=n; i)
if(du[i])dfs2(i);//走完剩下的环
printf("%dn",ans-sub);
if(ans-sub)for(int p=1;p;p=nxt[p])printf("%d ",s[p]);
return 0;
}ps：这题我断断续续补了五天，尤其是生日那天，本来希望做出这题来庆祝生日，很惨的是跨越了那天也没有做出来。后来只好看yt的代码才写出来。其实也不是很难啊，就是不容易想到准确的思路。
