noip 2018 d2t1 旅行
（题目来自洛谷）
给定n个城市，m条双向道路的图， 不存在两条连接同一对城市的道路，也不存在一条连接一个城市和它本身的道路。并且， 从任意一个城市出发，通过这些道路都可以到达任意一个其他城市。小 Y 只能通过这些道路从一个城市前往另一个城市。
小 Y 的旅行方案是这样的：任意选定一个城市作为起点，然后从起点开始，每次可 以选择一条与当前城市相连的道路，走向一个没有去过的城市，或者沿着第一次访问该 城市时经过的道路后退到上一个城市。当小 Y 回到起点时，她可以选择结束这次旅行或 继续旅行。需要注意的是，小 Y 要求在旅行方案中，每个城市都被访问到。(注意：同一条道路不能走两遍，也就是回头路只能走一次)
为了让自己的旅行更有意义，小 Y 决定在每到达一个新的城市（包括起点）时，将 它的编号记录下来。她知道这样会形成一个长度为 nn 的序列。她希望这个序列的字典序 最小，你能帮帮她吗？ 对于两个长度均为 n 的序列 A和 B，当且仅当存在一个正整数 x，满足以下条件时， 我们说序列 A 的字典序小于 B。
-
对于任意正整数 1≤i<x，序列A的第 i 个元素 Ai 和序列 B 的第 i 个元素 Bi 相同。
-
序列 A 的第 x 个元素的值小于序列 B 的第 x 个元素的值。
输入格式：
输入文件共 m + 1 行。第一行包含两个整数 n,m(m ≤ n)，中间用一个空格分隔。
接下来 m 行，每行包含两个整数 u,v (1 ≤ u,v ≤ n)，表示编号为 u 和 v 的城市之 间有一条道路，两个整数之间用一个空格分隔。
输出格式:
输出文件包含一行，n 个整数，表示字典序最小的序列。相邻两个整数之间用一个空格分隔。
输入输出样例：
输入样例#1：
6 5
1 3
2 3
2 5
3 4
4 6
输出样例#1：
1 3 2 5 4 6
输入样例#2：
6 6
1 3
2 3
2 5
3 4
4 5
4 6
输出样例#2：
1 3 2 4 5 6
说明
【数据规模与约定】
题解：
首先考虑m==n-1的情况，这种情况下，我们只需要先贪心的经过每个点所连向的点中最小的点，即可得到答案，直接用vector存图，对点进行排序，在树上dfs一遍即可解决，即可得到60分
考虑满分做法，因为n==m则图中有且只有一个环，可以想到这个环上肯定有一条边是不被需要的，因为我们只需要走一遍即可。
我们先找到环，枚举这个环上的每一条边删去，搜索更新答案的最小值，最后输出最小值即可，时间复杂度n^2
不找环直接暴力删边也可过
找环可以拓扑排序，可以并查集，这里采用一种其他的方法
#include<bits/stdc++.h>
#define maxn 5050
using namespace std;
struct node {
int v, w;
node(int vv) {
v = vv;
}
};
vector<node> G[maxn], g[maxn];
void adde(int a, int b) {
G[a].push_back(node(b));
G[b].push_back(node(a));
}
inline int getnum() {
int ans = 0; char c; int flag = 1;
while (!isdigit(c = getchar()) && c != '-');
if (c == '-') flag = -1; else ans = c - '0';
while (isdigit(c = getchar())) ans = ans * 10 + c - '0';
return ans * flag;
}
int n, m;
int vis[maxn];
int cnt = 0;
int ans[maxn], tmp[maxn];
int del[maxn][maxn];
int cmp(node a, node b) {
return a.v < b.v;
}
void dfs(int u, int f) {//假如n == m - 1，则直接贪心选取较小的边，对连向的点进行排序直接遍历图即可
ans[++cnt] = u;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].v;
if (v != f)
dfs(v, u);
}
}
int num;
int find(int u, int f) {//找环
if (num) return 0;//假如已经找到了环的起点，则退出搜索，因为此时环已经构建好了
vis[u] = 1;//已经遍历过这个点
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].v;
if (v == f) continue;
if (vis[v]) {//假如找到了遍历过的点，说明形成了环
num = v;//环的起点为num
g[u].push_back(node(v));//将构成环的这条边加入
return 1;//返回1，代表可以找到环
}
if (find(v, u)) {//假如从v开始能找到环的话
if (v == num) return 0;//如果连向的点就是起点，则返回，因为这条边不在环内
g[u].push_back(node(v));//将在环内的边加入图g
return 1;//返回可以找到环，这样就可以将一整个环内的边全部加入g
}
}
}
void dfs1(int u) {
if (vis[u]) return;
vis[u] = 1;
tmp[++cnt] = u;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].v;
if (del[u][v] == 0) dfs1(v);
}
}
int check() {
for (int i = 1; i <= n; i++) {
if (ans[i] == tmp[i]) continue;
if (ans[i] > tmp[i]) return 1;
else return 0;
}
}
int main() {
n = getnum(), m = getnum();
for (int i = 1; i <= m; i++) {
int a = getnum(), b = getnum();
adde(a, b);
}
for (int i = 1; i <= n; i++) {
sort(G[i].begin(), G[i].end(), cmp);//排序
}
for (int i = 1; i <= n; i++) {
ans[i] = n;//将ans赋值为最大值
}
if (n == m) {
find(1, -1);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < g[i].size(); j++) {
memset(vis, 0, sizeof(vis));
int v = g[i][j].v;
del[i][v] = 1; del[v][i] = 1;//删边
cnt = 0;
dfs1(1);
del[i][v] = 0; del[v][i] = 0;//恢复
if (check()) {
for (int i = 1; i <= n; i++) {
ans[i] = tmp[i];
}
}
}
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << " ";
}
return 0;
}
dfs(1, -1);
for (int i = 1; i <= cnt; i++) {
cout << ans[i] << " ";
}
return 0;
}