传送门;洛谷P5022 | MFOJ
作者:xzqiaochu
Solution
分两种情况
- M = N – 1
这是一棵树,贪心跑一遍DFS序即可。
有一点需要注意的是,要先预处理孩子节点排序,不然会最后三个点会超时。
- M = N
这是一棵基数树。
可以直接暴力删边,时间复杂度 O(N^2),大约 900ms 通过最后三个点(洛谷上测试的)。
正解的话,当然是先预处理出环所在的边。
Code
// A-旅行(travel)
// http://www.mfstem.org/contest/29/problem/A
// author: xzqiaochu
// status: AC
// time: 2019/11/06
// algorithm: 预处理每个节点的孩子排序
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using std::sort;
using std::vector;
const int NSZ = 5007, MSZ = NSZ * 2;
int n, m;
int head[NSZ];
struct Edge {
int from, to, next;
} edge[MSZ]; //预处理用
vector<int> g[NSZ]; //正式处理用
//init_dfs使用
bool flag, vis[NSZ]; //flag为dfs中断标记
int pre[NSZ];
int cyc_sta, use_edge[NSZ], cyc[NSZ]; //环所在的编号(id为奇数不变,偶数-1,防止双向边被重复统计)
//bool flag, vis[NSZ];
int del_x, del_y, tmp[NSZ], ans[NSZ];
inline void addEdge(int x, int y) {
static int tot = 0;
edge[++tot].to = y, edge[tot].from = x;
edge[tot].next = head[x], head[x] = tot;
g[x].push_back(y);
}
void init_sort() {
for (int i = 1; i <= n; i++)
sort(g[i].begin(), g[i].end());
}
void init_dfs(int x, int fa) {
if (vis[x]) {
pre[x] = 0; //环的起点
cyc_sta = fa; //环的终点
flag = true;
return;
}
vis[x] = true; //打标记
for (int i = head[x]; i; i = edge[i].next) {
if (flag) //在此处要立即判断中止信号
return; //如果下次进入递归再判断,会导致信息被修改
int y = edge[i].to;
if (y == fa)
continue;
//记录信息
pre[y] = x;
use_edge[y] = i;
init_dfs(y, x);
}
}
void init_cyc() {
int x = cyc_sta;
while (x) {
int from_edge;
if (use_edge[x] % 2 == 0) //id为奇数不变,偶数-1
from_edge = use_edge[x] - 1;
else
from_edge = use_edge[x];
cyc[++cyc[0]] = from_edge;
x = pre[x];
}
}
void dfs(int x, int fa) {
tmp[++tmp[0]] = x;
for (unsigned i = 0; i < g[x].size(); i++) {
int y = g[x][i];
if (y == fa)
continue;
if ((x == del_x && y == del_y) || (x == del_y && y == del_x))
continue;
dfs(y, x);
}
}
bool can() {
if (ans[1] == 0) //第一次
return true;
for (int i = 1; i <= n; i++)
if (ans[i] != tmp[i])
return tmp[i] < ans[i];
return false;
}
void update() {
if (can())
for (int i = 1; i <= n; i++)
ans[i] = tmp[i];
}
int main() {
// freopen("travel.in", "r", stdin);
// freopen("travel.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
addEdge(x, y), addEdge(y, x);
}
init_sort();
if (m == n - 1) {
dfs(1, 0);
for (int i = 1; i <= n; i++)
printf("%d ", tmp[i]);
} else {
init_dfs(1, 0); //检测环
init_cyc();
// puts("");
// for (int i = 1; i <= cyc[0]; i++)
// printf("%d ", cyc[i]);
// return 0;
//逐个删边
for (int i = 1; i <= cyc[0]; i++) { //枚举环上面的边号
int eid = cyc[i];
del_x = edge[eid].from, del_y = edge[eid].to; //删除边标记
tmp[0] = 0; //初始化
dfs(1, 0);
update();
}
for (int i = 1; i <= n; i++)
printf("%d ", ans[i]);
}
return 0;
}