题目描述

给出一个有 $n$ 个点，$n - 1$ 或 $n$ 条边的无向连通图，求 $dfs$ 遍历图的最小字典序

算法1

贪心地想，对每一个点的所有出边升序排序，优先走编号较小的点

如果是 $n - 1$ 条边，那么直接从 $1$ 号点出发 $dfs$ 遍历即可

如果是 $n$ 条边，那么图中存在一个简单环，删掉环中的任意一条边，图就变为树

枚举删除每一条边，从一号点出发 $dfs$ 序遍历，

如果能抵达所有点就说明删的是环中的边，就可以更新答案序列，否则图不连通

在 $dfs$ 时记录遍历序列，如果字典序大于答案序列直接return剪枝

还有一点要注意的是，由于删的边不保证是环上的，因此图可能是存在环的，此时不能用记录“回头路”来判重，需要一个判重数组

时间复杂度 $O(n^2)$

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>

using namespace std;

const int N = 5010;

struct Edge{
    int a, b;
}edges[N];

int n, m, k = -1;
vector<int> e[N];
vector<int> res, path;

bool st[N];
bool flag;      //  字典序是否小于res
bool dfs(int u)
{
    path.push_back(u);
    st[u] = true;

    if(path.back() < res[path.size() - 1])  flag = true;
    if(!flag and path.back() > res[path.size() - 1])  return false;

    for(int i : e[u])
        //  目标点非父节点且通过的不是删掉的那条边
        if(!st[i] and (k == -1 or !(u == edges[k].a and i == edges[k].b or u == edges[k].b and i == edges[k].a)))
        {
            if(!dfs(i))  return false;
        }

    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        e[a].push_back(b);
        e[b].push_back(a);
        edges[i] = {a, b};
    }

    for(int i = 1; i <= n; i ++)  sort(e[i].begin(), e[i].end());

    for(int i = n; i; i --)  res.push_back(i);      //初始化一个字典序最大的序列

    if(m == n - 1)
    {
        dfs(1);
        for(int i : path)  printf("%d ", i);
    } else {
        for(k = 0; k < m; k ++)
        {
            path.clear();
            flag = false;
            memset(st, 0, sizeof st);
            if(dfs(1) and path.size() == n)  res = path;
        }
        for(int i : res)  printf("%d ", i);
    }
    return 0;
}

算法2

无向图的双连通分量，tarjan找环

结果还TLE了，开了氧气才过

时间复杂度 $O(n^2)$

C++ 代码

#pragma GCC optimize(2)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>

using namespace std;

const int N = 5010;

struct Edge{
    int a, b;
};

int n, m, k = -1;
vector<int> e[N];
vector<int> res, path;
vector<Edge> edges;

int dfn[N], low[N], tot;

void tarjan(int u, int fa)
{
    dfn[u] = low[u] = ++ tot;

    for(int i : e[u])
    {
        if(i == fa)  continue;

        if(!dfn[i])
        {
            tarjan(i, u);
            low[u] = min(low[u], low[i]);

            //  子节点能抵达自己或自己上方，非桥
            if(low[i] <= dfn[u])  edges.push_back({u, i});
        }else
            low[u] = min(low[u], dfn[i]);
    }
}

bool flag;      //  字典序是否小于res
bool dfs(int u, int fa)
{
    path.push_back(u);
    if(path.back() < res[path.size() - 1])  flag = true;
    if(!flag and path.back() > res[path.size() - 1])  return false;

    for(int i : e[u])
        //  目标点非父节点且通过的不是删掉的那条边
        if(i != fa and (k == -1 or !(u == edges[k].a and i == edges[k].b or u == edges[k].b and i == edges[k].a)))
        {
            if(!dfs(i, u))  return false;
        }

    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        e[a].push_back(b);
        e[b].push_back(a);
    }

    for(int i = 1; i <= n; i ++)  sort(e[i].begin(), e[i].end());

    for(int i = n; i; i --)  res.push_back(i);      //初始化一个字典序最大的序列

    if(m == n - 1)
    {
        dfs(1, -1);
        for(int i : path)  printf("%d ", i);
    } else {

        tarjan(1, -1);

        for(k = 0; k < edges.size(); k ++)
        {
            path.clear();
            flag = false;
            if(dfs(1, -1))  res = path;
        }
        for(int i : res)  printf("%d ", i);
    }
    return 0;
}