[NOIp2018提高组]旅行：
题目大意：
一个\(n(n\le5000)\)个点，\(m(m\le n)\)条边的连通图。可以从任意一个点出发，前往任意一个相邻的未访问的结点，或沿着第一次来这个点的边返回。需要遍历每一个点。没经过一个新的结点，就将这个结点写下来。最终可以得到一个序列。求字典序最小的序列。
思路：
对于树的情况，显然从\(1\)出发，每次从字典序最小的相邻结点DFS即可。
对于有环的情况，由于环只有一个，我们可以将环找出来，枚举删掉环上的每一条边，然后按树的情况求解即可。
时间复杂度\(\mathcal O(n^2)\)。
源代码：
#include<set>
#include<stack>
#include<cstdio>
#include<cctype>
#include<vector>
#include<climits>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=5001;
struct Edge {
int u,v;
};
Edge edge[N];
std::vector<std::pair<int,int> > g[N];
bool vis[N],mark[N];
std::stack<std::pair<int,int> > stk;
void dfs(const int &x,const int &par) {
vis[x]=true;
for(unsigned i=0;i<g[x].size();i++) {
const int &y=g[x][i].first;
if(y==par) continue;
stk.push(std::make_pair(x,g[x][i].second));
if(!vis[y]) {
dfs(y,x);
} else {
int z;
do {
z=stk.top().first;
mark[stk.top().second]=true;
stk.pop();
} while(z!=y);
throw 0;
}
stk.pop();
}
}
std::set<int> e[N];
inline void add_edge(const int &u,const int &v) {
e[u].insert(v);
e[v].insert(u);
}
inline void del_edge(const int &u,const int &v) {
e[u].erase(v);
e[v].erase(u);
}
int s[N],ans[N];
void solve(const int &x,const int &par) {
s[++s[0]]=x;
for(std::set<int>::iterator i=e[x].begin();i!=e[x].end();i++) {
const int &y=*i;
if(y==par) continue;
solve(y,x);
}
}
inline bool check(int a[],int b[],const int &n) {
for(register int i=1;i<=n;i++) {
if(a[i]<b[i]) return true;
if(a[i]>b[i]) return false;
}
return false;
}
int main() {
const int n=getint(),m=getint();
for(register int i=0;i<m;i++) {
const int &u=edge[i].u=getint();
const int &v=edge[i].v=getint();
g[u].push_back(std::make_pair(v,i));
g[v].push_back(std::make_pair(u,i));
}
for(register int i=0;i<m;i++) {
add_edge(edge[i].u,edge[i].v);
}
if(m==n-1) {
solve(1,0);
for(register int i=1;i<=n;i++) {
printf("%d%c",s[i]," \n"[i==n]);
}
return 0;
}
try {
dfs(1,0);
} catch(...) {}
std::fill(&ans[1],&ans[n]+1,INT_MAX);
for(register int i=0;i<m;i++) {
if(!mark[i]) continue;
del_edge(edge[i].u,edge[i].v);
s[0]=0;
solve(1,0);
if(check(s,ans,n)) {
std::copy(&s[1],&s[n]+1,&ans[1]);
}
add_edge(edge[i].u,edge[i].v);
}
for(register int i=1;i<=n;i++) {
printf("%d%c",ans[i]," \n"[i==n]);
}
return 0;
}