HDU 3686 Traffic Real Time Query System（点双连通）

题意

给定一张 \(n\) 个点 \(m\) 条边的无向图，\(q\) 次询问，每次询问两边之间的必经之点个数。

思路

求两点之间必经之边的个数用的是边双缩点，再求树上距离。而对比边双和点双之后，我们不难发现点和边之间的对应关系，边双分量和点双分量的性质很多都是对称的。

边双	点双
两点之间至少有两条不共边的路径	两边之间至少有两条不共点的路径
边双间由桥边连接	点双内没有割点
边双间由桥边连接	点双间由割点连接

另外，一个点双也是一个特殊的边双，就像一个点仙人掌是一个特殊的边仙人掌一样。

那就容易看出本题就是一个点双缩点的裸题了。把所有的割点和点双分量拿出来，让每一个割点向它所在的点双分量连边即可。可能把图“缩成树”这种事本来就适合边双干，点双写起来不是很自然，也没什么办法。

代码

#include<bits/stdc++.h>

#define FOR(i, x, y) for(int i = (x), i##END = (y); i <= i##END; ++i)

#define DOR(i, x, y) for(int i = (x), i##END = (y); i >= i##END; --i)

template<typename T, typename _T> inline bool chk_min(T &x, const _T &y) {return y < x ? x = y, 1 : 0;}

template<typename T, typename _T> inline bool chk_max(T &x, const _T &y) {return x < y ? x = y, 1 : 0;}

typedef long long ll;

const int N = 10005;

const int M = 100005;

template<const int N, const int M, typename T> struct Linked_List

{

    int head[N], nxt[M], tot; T to[M];

    Linked_List() {clear();}

    T &operator [](const int x) {return to[x];}

    void clear() {memset(head, -1, sizeof(head)), tot = 0;}

    void add(int u, T v) {to[tot] = v, nxt[tot] = head[u], head[u] = tot++;}

    #define EOR(i, G, u) for(int i = G.head[u]; ~i; i = G.nxt[i])

};

Linked_List<N, M << 1, int> G;

Linked_List<N << 1, N << 2, int> T;

int dfn[N], low[N], stk[M], bel[M], dfn_idx, bcc, tp, tot;

bool mark[M];

int fa[N << 1], dep[N << 1], sz[N << 1], son[N << 1], top[N << 1];

int n, m, q;

void tarjan(int u, int fa_e)

{

    dfn[u] = low[u] = ++dfn_idx;

    EOR(i, G, u)

    {

        if(i == (fa_e ^ 1)) continue;

        int v = G[i];

        if(!dfn[v])

        {

            stk[++tp] = i;

            tarjan(v, i), chk_min(low[u], low[v]);

            if(low[v] >= dfn[u])

            {

                bcc++;

                do bel[stk[tp] / 2] = bcc;

                while(stk[tp--] != i);

            }

        }

        else if(dfn[v] < dfn[u])

        {

            stk[++tp] = i;

            chk_min(low[u], dfn[v]);

        }

    }

}

void dfs(int u, int f, int d)

{

    fa[u] = f, dep[u] = d, sz[u] = 1, son[u] = 0;

    EOR(i, T, u)

    {

        int v = T[i];

        if(v == f) continue;

        dfs(v, u, d + 1);

        sz[u] += sz[v];

        if(sz[v] > sz[son[u]]) son[u] = v;

    }

}

void hld(int u, int tp)

{

    top[u] = tp;

    if(son[u]) hld(son[u], tp);

    EOR(i, T, u)

    {

        int v = T[i];

        if(v == fa[u] || v == son[u]) continue;

        hld(v, v);

    }

}

int get_lca(int u, int v)

{

    while(top[u] != top[v])

    {

        if(dep[top[u]] < dep[top[v]]) std::swap(u, v);

        u = fa[top[u]];

    }

    return dep[u] < dep[v] ? u : v;

}

int get_dis(int u, int v)

{

    int lca = get_lca(u, v);

    return dep[u] + dep[v] - 2 * dep[lca];

}

int main()

{

    while(scanf("%d%d", &n, &m), (n || m))

    {

        G.tot = T.tot = 0;

        FOR(i, 1, n) G.head[i] = -1, dfn[i] = 0;

        FOR(i, 1, 2 * n) T.head[i] = -1, dep[i] = 0;

        bcc = dfn_idx = tp = 0;

        FOR(i, 1, m)

        {

            int u, v;

            scanf("%d%d", &u, &v);

            G.add(u, v), G.add(v, u);

        }

        FOR(i, 1, n) if(!dfn[i]) tarjan(i, -1);

        tot = bcc;

        FOR(u, 1, n)

        {

            tp = 0;

            EOR(i, G, u)

            {

                if(!mark[bel[i / 2]])

                {

                    mark[bel[i / 2]] = 1;

                    stk[++tp] = bel[i / 2];

                }

            }

            if(tp >= 2)

            {

                tot++;

                FOR(i, 1, tp) T.add(tot, stk[i]), T.add(stk[i], tot);

            }

            while(tp) mark[stk[tp]] = 0, tp--;

        }

        FOR(i, 1, tot) if(!dep[i]) dfs(i, 0, 1), hld(i, i);

        scanf("%d", &q);

        while(q--)

        {

            int e1, e2;

            scanf("%d%d", &e1, &e2);

            e1--, e2--;

            printf("%d\n", get_dis(bel[e1], bel[e2]) / 2);

        }

    }

    return 0;

}

巴特西

HDU 3686 Traffic Real Time Query System（点双连通）

题意

思路

代码

最新文章

热门文章