基环树

简介

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

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$ 分别在哪棵树上即可

   建图大概是这样：

   牛客 contest 12986E Shortest Path Sum