「模板」圆方树

本文主要是介绍「模板」圆方树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

对每个点双新建一个方点，并把点双内的点向它连边。

CF1045C Hyperspace Highways

#include <bits/stdc++.h>
#define ll long long
#define db double
#define gc getchar
#define pc putchar
#define pb push_back

using namespace std;

namespace IO
{
    template <typename T>
    void read(T &x)
    {
        x = 0; bool f = 0; char c = gc();
        while(!isdigit(c)) f |= c == '-', c = gc();
        while(isdigit(c)) x = x * 10 + c - '0', c = gc();
        if(f) x = -x;
    }

    template <typename T, typename ...Args>
    void read(T &x, Args &...args) {read(x), read(args...);}

    template <typename T>
    void write(T x)
    {
        if(x < 0) pc('-'), x = -x;
        if(x > 9) write(x / 10);
        pc('0' + x % 10);
    }
}
using namespace IO;

const int N = 2e5 + 5;

int n, m, q;
vector <int> G[N];
vector <int> T[N];
int dfn[N], low[N], tim;
int cnt;
int stk[N], tp;

void tarjan(int u)
{
    dfn[u] = low[u] = ++tim;
    stk[++tp] = u;
    for(auto v : G[u])
    {
        if(!dfn[v])
        {
            tarjan(v), low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u])
            {
                cnt++;
                T[cnt].pb(u), T[u].pb(cnt);
                T[cnt].pb(v), T[v].pb(cnt);
                while(stk[tp] != v)
                {
                    int x = stk[tp--];
                    T[cnt].pb(x), T[x].pb(cnt);
                } tp--;
            }
        } else low[u] = min(low[u], dfn[v]);
    }
    return;
}

int fa[N], dep[N], siz[N], son[N];

void dfs1(int u, int f)
{
    fa[u] = f, dep[u] = dep[f] + 1, siz[u] = 1;
    for(auto v : T[u])
    {
        if(v == f) continue;
        dfs1(v, u); siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
    return;
}

int top[N];

void dfs2(int u, int tp)
{
    top[u] = tp;
    if(son[u]) dfs2(son[u], tp);
    for(auto v : T[u])
        if(v != fa[u] && v != son[u]) dfs2(v, v);
    return;
}

int LCA(int x, int y)
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}

int Dis(int x, int y)
{
    return (dep[x] + dep[y] - dep[LCA(x, y)] * 2) / 2;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    read(n, m, q); cnt = n;
    for(int i = 1, u, v; i <= m; i++)
        read(u, v), G[u].pb(v), G[v].pb(u);
    tarjan(1), dfs1(1, 0), dfs2(1, 1);
    while(q--)
    {
        int x, y; read(x, y);
        write(Dis(x, y)), pc('\n');
    }
    return 0;
}
// A.S.

这篇关于「模板」圆方树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！