原题大意
给定一个无向图，有n个点，m条边，让你求出一条路径，这条路径有3个满足条件：
- 这条路径至少穿过两个点
- 这条路径只经过一个点一次
- 任何与起点或终点相邻的点一定包括在这条路径里面
题目输入保证存在路径，并且多条路径时，输出任意一条
算法分析
可以从任意一点开始（记为x）。把x放到一个双端队列里，以之为起点。
然后重复执行一下内容：
- 如果有与之相邻的点且不在队列里的，就将其放到队首，并以之为起点。
- 如果有与队尾相邻（终点）且不在队列里，就将其放到队尾，并以之为终点。
直到队首队尾没有点与之相邻，或相邻的都在队列里，输出队列。
程序代码
#include <cstdio>
#include <vector>
#include <deque>
#include <memory.h>
#define mem(a,b) memset(a, b, sizeof(a))
using namespace std;
const int maxn = 1e5+5;
bool vis[maxn];
vector<int> vex;
vector<int> G[maxn];
deque<int> dq;
int n, m;
void Init(){
mem(vis,0);
vex.clear();
dq.clear();
for(int i = 0; i <= n; i++){
G[i].clear();
}
}
int main(){
while(scanf("%d %d", &n, &m) != EOF){
int x, y;
Init();
for(int i = 0; i < m; i++)
{
scanf("%d %d",&x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
dq.push_back(1);
vis[1] = true;
bool fg = true, fg2 = true;
while(fg || fg2){
fg = false;
int st = dq.front();
for(int i = 0; i < G[st].size(); i++){
if(!vis[G[st][i]])
{
vis[G[st][i]] = true;
dq.push_front(G[st][i]);
fg = true;
break;
}
}
fg2 = false;
int ed = dq.back();
for(int i = 0; i < G[ed].size(); i++){
if(!vis[G[ed][i]])
{
vis[G[ed][i]] = true;
dq.push_back(G[ed][i]);
fg2 = true;
break;
}
}
}
printf("%d\n", dq.size());
while(!dq.empty()){
printf("%d ", dq.front());
dq.pop_front();
}
printf("\n");
}
return 0;
}