基环树 | 梦始

图中只存在一个环的图就是基环树，
分为有向图和无向图

无向图求基环树可以使用bfs ：先统计入度，然后每次对队列中元素删边，把删后度数为1的点入队，bfs结束后，所有度数 > 1的点就是环上的点，如果只需要求一个点，可以使用dfs，出现了两次的点说明必然有环。

想法1 ：可以通过先找出基环树的环，之后分别对除了环以外的每个点的子树进行操作，把信息合并到环上，之后问题就集中为处理一个环上问题，

想法2 ：可以先找出基环树的环，之后删掉基环树上某一条边，将基环树变成一个树，处理树上问题

寻找环的办法

1 ：对于无向图，使用拓补排序，最后剩下的度数 > 1 的点就是环上的点

2 : 对于有向图，使用dfs 寻找，出现了vis两次的点就是环上一个点

auto check_c = [&](auto self, i64 u) -> int {
        vis[u] = 1;
        int now = fa[u];
        if (vis[now]) return now;
        else return self(self, now);
};

记录深度并返回环内元素个数的板子 :

vector<int> vis(n + 1);
vector<int> h(n + 1);
int flag = 0;
auto check_c = [&](auto self, int u, int cnt) -> void {
    h[u] = cnt;
    vis[u] = 1;
    for (auto v : e[u]) {
        if (!vis[v]) {
            self(self, v, cnt + 1);
        }
        else if (vis[v] == 1) {
            ++flag, siz.push_back(h[u] - h[v] + 1);
        }
    }
    vis[u] = 2;
};

使用并查集寻找环上两个断点 : （适用于无向图断环）
每次输入点的时候将点并入一个并查集，如果输入的点已经在一个集合里面，说明这两个点连接后会形成环，直接记录下两个断点的位置
1
点击跳转 : 例题1 :
骑士
前置知识：树形dp， P1352没有上司的舞会，对于颗树，从根开始跑一遍dp，使用dp【x】【1 / 0 】， x表示当前的节点，1或者0表示当前节点取或者不取，使用回溯转移，从叶子到节点更新答案，其中，对于每一个节点u，用v表示他的子节点，有：
1
2
dp[u][1] = ∑dp[v][0]
dp[u][0] = ∑max(dp[v][1], dp[v][0]);
将所有节点更新完得到答案，对于这道骑士，就是在原题的基础上增加了一条边，使得原来的树里面出现了环，变成一个基环森林， solution :

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<int>> e(n + 1);
    vector<vector<i64>> dp(n + 1, vector<i64> (3));
    vector<int> fa(n + 1);
    vector<i64> val(n + 1);
    int mark;
    vector<bool> vis(n + 1);

    for (int i = 1; i <= n; i++) {
        int u;
        cin >> val[i] >> u;
        e[u].push_back(i); 
        fa[i] = u;
    }

    auto dfs = [&](auto self, int u) -> void {
        dp[u][0] = 0;
        dp[u][1] = val[u];
        vis[u] = true;

        for (auto v : e[u]) {
            if (v == mark) continue;
            self(self, v);
            dp[u][1] += dp[v][0];
            dp[u][0] += max(dp[v][1], dp[v][0]);
        }
    };

    auto find = [&](auto self, i64 u) -> int {
        vis[u] = 1;
        int now = fa[u];
        if (vis[now]) return now;
        else return self(self, now);
    };

    i64 ans = 0;
    for (int i = 1; i <= n; i++) if (!vis[i]) {
        i64 res = 0;
        mark = find(find, i);
        dfs(dfs, mark);
        res = max(res, dp[mark][0]);
        mark = fa[mark];
        dfs(dfs, mark);
        res = max(res, dp[mark][0]);
        ans += res;
    }

    cout << ans << '\n';
    return 0;
}

例题2 ：

追逐游戏
本题如果使用上面的思路，很难实现，不如采用先找出环，之后对于环上每一个点处理，使其满足条件 :

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<vector<int>> e(n + 1);
    for (int i = 1; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    vector<int> f(n + 1), dfn(n + 1);
    int dfncnt = 0, siz = 0;
    vector<int> cycle;

    auto dfs1 = [&](auto self, int u, int Fa) -> void {
        dfn[u] = ++dfncnt;
        f[u] = Fa;
        for (auto v : e[u]) {
            if (v == Fa) continue;
            if (!dfn[v]) {
                self(self, v, u);
            }
            else if (dfn[v] > dfn[u]) {
                while (v != u) {
                    cycle.push_back(v);
                    siz++;
                    v = f[v];
                }
                cycle.push_back(v);
                siz++;
            }
        }
    };



    vector<int> dep(n + 1), root(n + 1);
    auto dfs2 = [&](auto self, int u, int fa, int Root) -> void {
        dep[u] = dep[fa] + 1;
        root[u] = Root;
        for (auto v : e[u]) {
            if (v == fa || dfn[v]) continue;
            self(self, v, u, Root);
        }
    };

    dfs1(dfs1, 1, 0);

    for (int i = 1; i <= n; i++) dfn[i] = 0; // 转vis

    for (auto x : cycle) {
        //cerr << x << ' ';
        dfn[x] = 1;
    }
    
    for (int i = 0; i < siz; i++) {
        dfs2(dfs2, cycle[i], 0, cycle[i]);
        dep[cycle[i]] = i + 1;
    }

    while (q--) {
        int a, b;
        cin >> a >> b;

        if (siz == 0) cout << "Deception\n";
        else if (dfn[a]) cout << "Survive\n";
        else {
            int ned1 = dep[a] - 1;
            int ned2 = min(abs(dep[root[b]] - dep[root[a]]);
            int siz - abs(dep[root[b]] - dep[root[a]]));
            if (!dfn[b]) ned2 += dep[b] - 1;
            if (ned1 < ned2) {
                //cerr << ned1 << ned2 << '\n';
                cout << "Survive\n";
            }
            else {
                cout << "Deception\n";
            }
        }
    }
    return 0;
}