洛谷P5022 旅行 题解 去环/搜索

题目链接：https://www.luogu.org/problem/P5022
这道题目一开始看的时候没有思路，但是看到数据范围里面有一个：
\(m = n-1\) 或 \(m = n\) ，一下子有了思路。
当 \(m = n-1\) 时，这就是一棵树，以1为根节点进行搜索，每次优先访问编号小的点即可。
当 \(m = n\) 时，可知只有一个环，找到环中对应的所有边，然后遍历每一条环中的边，假设删除它，然后就变成了一棵树。
时间复杂度为：\(O(n^2)\) 。
实现代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5050;
struct Node {
    int u, v, id;
    Node() {}
    Node(int _u, int _v, int _id) { u = _u; v = _v; id = _id; }
} edge[maxn*2], loop_edge[maxn];
vector<Node> g[maxn];
int n, m, p[maxn], pe[maxn], cnt, depth[maxn];
bool vis[maxn], vise[maxn*2], marked[maxn*2];
int ans_seq[maxn], tmp_seq[maxn], ans_cnt, tmp_cnt;
bool cmp(Node a, Node b) {
    return a.v < b.v;
}

void find_loop(int u, int pre, int d) {
    vis[u] = true;
    depth[u] = d;
    int sz = g[u].size();
    for (int i = 0; i < sz; i ++) {
        int v = g[u][i].v, id = g[u][i].id;
        if (v == pre) continue;
        if (!vis[v]) {
            vise[id] = vise[id^1] = true;
            p[v] = u;
            pe[v] = id;
            find_loop(v, u, d+1);
        }
    }
}

void select_loop_edges(int u, int v, int id) {
    loop_edge[cnt++] = Node(u, v, id);
    while (u != v) {
        if (depth[u] > depth[v]) {
            loop_edge[cnt++] = Node(p[u], u, pe[u]);
            u = p[u];
        }
        else if (depth[u] < depth[v]) {
            loop_edge[cnt++] = Node(p[v], v, pe[v]);
            v = p[v];
        }
        else {
            loop_edge[cnt++] = Node(p[u], u, pe[u]);
            u = p[u];
            loop_edge[cnt++] = Node(p[v], v, pe[v]);
            v = p[v];
        }
    }
}

void dfs(int u, int pre) {
    tmp_seq[tmp_cnt++] = u;
    int sz = g[u].size();
    for (int i = 0; i < sz; i ++) {
        int v = g[u][i].v, id = g[u][i].id;
        if (v == pre || marked[id] || marked[id^1]) continue;
        dfs(v, u);
    }
}

void final_check() {
    bool flag = false;
    if (ans_seq[0]) {
        for (int i = 0; i < n; i ++) {
            if (ans_seq[i] > tmp_seq[i]) { flag = true; break; }
            else if (ans_seq[i] < tmp_seq[i]) break;
        }
    }
    else 
        flag = true;
    if (flag) for (int i = 0; i < n; i ++) ans_seq[i] = tmp_seq[i];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i ++) {
        int u, v, w;
        scanf("%d%d", &u, &v);
        g[u].push_back(Node(u, v, i*2));
        g[v].push_back(Node(v, u, i*2+1));
        edge[i*2] = Node(u, v, i*2);
        edge[i*2+1] = Node(v, u, i*2+1);
    }
    for (int i = 1; i <= n; i ++) sort(g[i].begin(), g[i].end(), cmp);
    if (m == n) {
        find_loop(1, -1, 1);
        for (int i = 0; i < 2*m; i += 2) {
            if (!vise[i]) {
                int u = edge[i].u, v = edge[i].v;
                select_loop_edges(u, v, i);
                break;
            }
        }
        for (int i = 0; i < cnt; i ++) {
            marked[loop_edge[i].id] = marked[loop_edge[i].id^1] = true;
            tmp_cnt = 0;
            dfs(1, -1);
            final_check(); 
            marked[loop_edge[i].id] = marked[loop_edge[i].id^1] = false;
        }
    }
    else {  // m == n-1
        dfs(1, -1);
        final_check();
    }
    for (int i = 0; i < n; i ++) {
        if (i) putchar(' ');
        printf("%d", ans_seq[i]);
    }
    puts("");
    return 0;
}

洛谷P5022 旅行 题解 去环/搜索

原文：https://www.cnblogs.com/codedecision/p/11782501.html