思路:
记录并排序各个点的所能到达的下一个点的编号,然后从1号点出发。
题目说m <= n, 说明m的值有两种:
若 m == n - 1, 那这就是一个普通的树,走一遍dfs即可。
若 m == n, 那这就是一颗基环树。基环树是一种有 n 个点 n 条边的图,
简单地讲就是树上在加一条边。相比树它出现了一个环,因此称为基环树。
如果是基环树,我们要先考虑枚举删掉某条边,然后再进行dfs, 对比删掉各条边后的路径是否更佳。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <cstring>
const static int N = 5100;
vector<int> e[N];
using PII = pair<int, int>;
PII edges[N];
int s[N]; //记录某个点是否被访问过
vector<int> path(N, N); //记录路径
int cnt; //路径指针,指向当前路径的最后一个节点
bool better; //是否找到更佳路径,只要找到一个点更佳,则当前路径更佳, 往后无需判断
int n, m;
int del_u, del_v; //断边的两个顶点
void add(int a, int b)
{
e[a].push_back(b);
e[b].push_back(a);
}
bool dfs(int u)
{
if (!better) //如果还不确定当前路径是否是最佳的
{
//和上一个路径方案的该位置节点比较,是否更优
if (u < path[cnt]) better = true; // 已经可以确定是更好的路径了
if (u > path[cnt]) return true; // 可以确定不是更好的路径了,没有必要继续往下走了,直接短路
}
s[u] = true;
path[cnt++] = u; // 把当前点加入到路径中
for (int i = 0; i < e[u].size(); ++i) //枚举当前节点的所有邻接点
{
int v = e[u][i];
if (s[v]) continue;
//判断是否为断边
if (u == del_u && v == del_v) continue;
if (v == del_u && u == del_v) continue;
if (dfs(e[u][i])) return true;
}
return false;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; ++i)
{
int u, v;
cin >> u >> v;
add(u, v);
edges[i] = { u, v };
}
//排序所有点的出度端点
for (int i = 1; i <= n; ++i)
{
sort(e[i].begin(), e[i].end());
}
if (m == n - 1) dfs(1);
else if (m == n) //基环树
{
//暴力删边
for (int i = 1; i <= m; ++i) //枚举边
{
del_u = edges[i].first, del_v = edges[i].second;
memset(s, false, sizeof s);
cnt = 0, better = false;
dfs(1);
}
}
for (int i = 0; i < n; ++i)
{
cout << path[i] << " ";
}
}