P2783 有机化学之神偶尔会作做弊 题解

2021年11月24日 阅读数:4
这篇文章主要向大家介绍P2783 有机化学之神偶尔会作做弊 题解,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Description

Luogu传送门node

Solution

\(Tarjan\) 边双缩点 + 树剖求 \(lca\)c++

其实就是个板子可是我卡了一夜QwQgit

因为是无向图,因此先跑一遍 \(Tarjan\) 找到全部的,而后 dfs 遍历整张图,找到全部的边双连通份量,每一个边双指定一个新编号,而后再在边双之间连边建新图。spa

建完图以后利用树剖(或者其余什么都行)求个 \(lca\),再树上差分一下便可。code

坑点:ip

  • 此题有重边,重复的边只能加一遍,我用的 hash + map 实现的吗,把边 hash 一下而后map标记一下。
  • 建新图的时候必定要用边双的编号建。
  • 查询 \(lca\) 的时候也是边双的编号啊啊啊啊啊啊啊(由于这个卡了一夜,感谢 LawrenceSivan 巨佬帮我看出问题)

Code

#include <bits/stdc++.h>

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 1) write(x / 2);
        putchar(x % 2 + '0');
    }
}
using namespace IO;

const int N = 1e5 + 1;
const int M = 5e5 + 1;
unordered_map <int, bool> mp;
int n, m, q;
struct node{
    int u, v, nxt;
}edge[M << 1];
int head[N], tot = 1;
int bri[N << 1];

inline void add(int x, int y){
    edge[++tot] = (node){x, y, head[x]};
    head[x] = tot;
}

namespace Tarjan{
    int dfn[N], low[N], tim;
    int stk[N], top;
    bool vis[N];
    int cnt, scc[N];
    queue <int> que;

    inline void tarjan(int x, int e){
        dfn[x] = low[x] = ++tim;
        for(int i = head[x]; i; i = edge[i].nxt){
            int y = edge[i].v;
            if(e == (i ^ 1)) continue;
            if(!dfn[y]){
                tarjan(y, i), low[x] = min(low[x], low[y]);
                if(low[y] > dfn[x]) bri[i] = bri[i ^ 1] = 1;
            }else low[x] = min(low[x], dfn[y]);
        }
    }

    inline void dfs(int x){
        vis[x] = 1;
        que.push(x);
        for(int i = head[x]; i; i = edge[i].nxt){
            int y = edge[i].v;
            if(!vis[y] && !bri[i]) dfs(y);
        }
    }
}
using namespace Tarjan;

namespace Cut_Tree{
    int siz[N], son[N], fa[N], dep[N];
    int top[N], dfn[N], tim;
    vector <int> g[N];

    inline void dfs1(int x, int p){
        fa[x] = p, dep[x] = dep[p] + 1, siz[x] = 1;
        for(auto y : g[x]){
            if(y == p) continue;
            dfs1(y, x);
            siz[x] += siz[y];
            if(siz[y] > siz[son[x]]) son[x] = y;
        }
    }

    inline void dfs2(int x, int topfa){
        dfn[x] = ++tim, top[x] = topfa;
        if(!son[x]) return;
        dfs2(son[x], topfa);
        for(auto y : g[x]){
            if(y == fa[x] || y == son[x]) continue;
            dfs2(y, y);
        }
    }

    inline 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;
    }
}
using namespace Cut_Tree;

int main(){
    n = read(), m = read();
    for(int i = 1; i <= m; ++i){
        int u = read(), v = read();
        if(u > v) swap(u, v);
        if(!mp[u * n + v]) add(u, v), add(v, u), mp[u * n + v] = 1;//判重边,不知道这样写对不对 QwQ
    }
    for(int i = 1; i <= n; ++i)//找桥
        if(!Tarjan::dfn[i]) tarjan(i, 1);
    for(int i = 1; i <= n; ++i){//找到全部联通块
        if(!vis[i]){
            dfs(i), cnt++;
            while(!que.empty())
                scc[que.front()] = cnt, que.pop();
        }
    }
    mp.clear();
    for(int i = 2; i <= tot; ++i){//建新树
        int u = scc[edge[i].u], v = scc[edge[i].v];
        if(u > v) swap(u, v);
        if(u != v && !mp[u * n + v]){
            g[u].push_back(v), g[v].push_back(u);
            mp[u * n + v] = 1;
        }
    }
    dfs1(1, 0), dfs2(1, 1);
    q = read();
    while(q--){
        int x = scc[read()], y = scc[read()];
        write(dep[x] + dep[y] - (dep[lca(x, y)] << 1) + 1), puts("");
    }
    return 0;
}

\[\_EOF\_ \]