解法
首先比较显然的是肯定要确定1为根
1.对于树的情况,我们根据贪心策略,每次走当前节点儿子中序号最小的那个
2.对于 n == m 的情况 我们会发现当前图中一定有环,那么我们需要每次删去环上的一条边,将其变为树的情况来做。
如何找环上的边 :我们仔细观察会发现,当枚举到一条边时,如果这条边连接的两点中有一个点只有一个儿子,那么说明这条边一定不是环上的边。
然后就是比较路径了。
在比较路径时,我一开始的写法比较暴力,每次找完后比对:
for(int j = 0; j < tmp.size(); j++) {
if(path[j] == tmp[j]) continue;
else {
if(path[j] > tmp[j]) {
path = tmp;
break;
}
else break;
}
}
但这样最慢的一个点居然跑了997ms,评测机一慢就会T
所以我们不妨加一个可行性剪枝
if(path.size()) {
int ed = tmp.size() - 1;
if(tmp[ed] != path[ed]) {
if(tmp[ed] > path[ed] && !reaf) {
x = 1;
return;
}
else reaf = 1;
}
}
这样总体时间比之前的写法快了20倍,最慢的一个点只跑了29ms
这就是算法的魅力啊!
C++ 代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e4 + 10;
int n, m;
int vis[N];
vector<int> st[N];
vector<int> path;
int id;
struct node {
int u, v;
}t[N];
void dfs1(int u) {
for(int i = 0; i < st[u].size(); i++) {
int v = st[u][i];
if(!vis[v]) {
vis[v] = 1;
path.push_back(v);
dfs1(v);
}
}
}
int d1, d2;
vector<int> tmp;
bool x, reaf;
void dfs2(int u) {
if(path.size()) {
int ed = tmp.size() - 1;
if(tmp[ed] != path[ed]) {
if(tmp[ed] > path[ed] && !reaf) {
x = 1;
return;
}
else reaf = 1;
}
}
for(int i = 0; i < st[u].size(); i++) {
int v = st[u][i];
if(u == d1 && v == d2) continue;
else if(v == d1 && u == d2) continue;
if(!vis[v]) {
vis[v] = 1;
tmp.push_back(v);
dfs2(v);
if(x) return;
}
}
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
st[u].push_back(v);
st[v].push_back(u);
t[++id].u = u, t[id].v = v;
}
for(int i = 1; i <= n; i++) sort(st[i].begin(), st[i].end());
if(n != m) {
vis[1] = 1;
path.push_back(1);
dfs1(1);
for(int i = 0; i < path.size(); i++) printf("%d ", path[i]);
}
else{
for(int i = 1; i <= id; i++) {
tmp.clear();
memset(vis, 0, sizeof vis);
x = reaf = 0;
vis[1] = 1;
tmp.push_back(1);
d1 = t[i].u, d2 = t[i].v;
if(st[d1].size() == 1 || st[d2].size() == 1) continue;
dfs2(1);
// for(int i = 0; i < tmp.size(); i++) cout << tmp[i] << " " ;
// cout << endl;
if(!path.size()) {
path = tmp;
continue;
}
if(!x) {
path = tmp;
}
// for(int j = 0; j < tmp.size(); j++) {
// if(path[j] == tmp[j]) continue;
// else {
// if(path[j] > tmp[j]) {
// path = tmp;
// break;
// }
// else break;
// }
// }
}
for(int i = 0; i < n; i++) printf("%d ", path[i]);
}
return 0;
}