DDOSvoid's Blog

基环树

发表于 更新于 分类于
本文字数： 766 阅读时长 ≈ 1 分钟

简介

关于如何找环，直接 $dfs$ 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int a[maxn], cnt; 
bool Dfs(int u, int fa) {
    static bool vis[maxn] = { 0 };
    static stack<int> S; 
    vis[u] = 1; S.push(u);
    for (auto v : G[u]) {
        if (v == fa) continue;
        if (vis[v]) {
            int t;
            do {
                t = S.top(); S.pop();
                a[++cnt] = t; 
            } while (t != v); 
            return 1; 
        }
        if (Dfs(v, u)) return 1; 
    } S.pop(); return 0; 
}

例题

  1. 简要题意：给定一棵基环树，求从 $1$ 开始 $dfs$ 所能得到的字典序最小的 $dfs$ 序

    $n\le 5\times 10^5$

    简要题解：注意到如果是一棵树的情况，那么我们从 $1$ 开始 $dfs$ 每次走编号最小的节点即可

    考虑基环树的情况，发现最终一定有一条边没有经过，所以我们枚举删边即可

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

    Luogu P5022 [NOIP2018 提高组] 旅行

  2. 简要题意：给定一个 $n$ 个点的基环树，现在有 $m$ 次询问，每次询问给定三元组 $(x,y,z)$，求一个点 $k$，使得 $d(x,k)+d(y,k)+d(z,k)$ 最小，$d(x,y)$ 表示 $x$ 到 $y$ 的最短路径

    $n\le 10^5$

    简要题解：如果不是基环树，那么答案显然是 $\frac{d(x,y)+d(x,z)+d(y,z)}{2}$，否则我们按照一种比较神奇的建树方法，建三棵树，然后枚举 $x,y,z$ 分别在哪棵树上即可

    建图大概是这样：

    xzkRzj.png牛客 contest 12986E Shortest Path Sum