2018 D2t1 旅行
https://www.luogu.com.cn/problem/P5022
题意
- 给出一个有 n 个点，n?1或 n 条边的无向连通图，求 dfs遍历图的最小字典序
想法
- bfs+ 剪枝
- 一共有两种情况，n=m就是基环数（也就是只有一个环的树，n=m）
- 情况二：就是普通树。用dfs遍历。找到最小字典的序列
- 情况一：也不需要找到环。只需要将每条边都删除一次（不是真的删除，只是将其标记）。判断是否遍历过所有的点了。（cnt == n）是的话，说明删除的边就是环中的边。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>using namespace std;typedef pair<int, int> PII;const int N = 5010;int n, m;
//e[i]保存i点的相连的点。可能用多条
vector<int> e[N];
//边
PII edge[N];
//需要删除的边，不是真的删除，只是将其标记
int del_u, del_v;
//构造函数，N个元素，先赋值为N
vector<int> ans(N, N);
//构造函数，N个元素
vector<int> path(N);
//是否访问的数组
bool st[N];
//cnt,dfs中访问过cnt个节点
//state = -1 表示下一次不会被剪纸
int cnt, state;//dfs返回bool表示是否要跳出，也就是剪纸
bool dfs(int u)
{//判断剪枝if (!state){//当前的数字大于答案中的值 剪纸if (u > ans[cnt]) return true;if (u < ans[cnt]) state = -1;}//访问过，且加入pathst[u] = true;path[cnt ++ ] = u;//dfs核心,便利u的直接节点for (int i = 0; i < e[u].size(); i ++ ){//x为u的相连点int x = e[u][i];//如果，x,u连边不是需要删除的边的话，dfs下去if (!(x == del_u && u == del_v) && !(x == del_v && u == del_u) && !st[x])if (dfs(x)) return true;}return false;
}int main()
{scanf("%d%d", &n, &m);//输入边，且把a,b的相连点加入for (int i = 0; i < m; i ++ ){int a, b;scanf("%d%d", &a, &b);e[a].push_back(b);e[b].push_back(a);edge[i] = {a, b};}//排序每个节点的相连点。减少了dfs的深度和次数for (int i = 1; i <= n; i ++ ) sort(e[i].begin(), e[i].end());//情况一：基环树if (n == m){//将每条边都试试删除for (int i = 0; i < m; i ++ ){//记录删除边的节点del_u = edge[i].first, del_v = edge[i].second;memset(st, false, sizeof st);cnt = state = 0;dfs(1);if (cnt == n) ans = path;}}//情况二：普通树else{dfs(1);if (cnt == n) ans = path;}for (int i = 0; i < n; i ++ ) printf("%d ", ans[i]);return 0;
}