【洛谷 P2783】有机化学之神偶尔会做作弊（双联通分量）

题目链接

可能是除了《概率论》的最水的黑题了吧

用\(Tarjan\)缩点（点双联通分量），然后就是树上两点之间的距离了，跑\(LCA\)就好了。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int s; char ch;

inline int read(){

    s = 0; ch = getchar();

    while(ch < '0' || ch > '9') ch = getchar();

    while(ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); }

    return s;

}

const int MAXN = 10010;

const int MAXM = 50010;

int dfn[MAXN], low[MAXN], id, bridge[MAXM << 1], dcc, belong[MAXN], top, vis[MAXN];

int n, m, a, b, head[MAXN], num = 1, f[MAXN][20], dep[MAXN], t, stack[MAXN];

struct Edge{

    int from, next, to;

}e[MAXM << 2];

inline void Add(int from, int to){

    e[++num].to = to; e[num].from = from; e[num].next = head[from]; head[from] = num;

    e[++num].to = from; e[num].from = to; e[num].next = head[to]; head[to] = num;

}

void Tarjan(int u, int fa){

    dfn[u] = low[u] = ++id; stack[++top] = u; vis[u] = 1;

    for(int i = head[u]; i; i = e[i].next)

       if(e[i].to != fa)

         if(!dfn[e[i].to]){

           Tarjan(e[i].to, u);

           low[u] = min(low[u], low[e[i].to]);

         }

         else if(vis[e[i].to])

           low[u] = min(low[u], dfn[e[i].to]);

    if(dfn[u] == low[u]){

      ++dcc;

      do

        belong[stack[top]] = dcc;

      while(stack[top--] != u);

    }

}

void getDF(int u, int fa){

    f[u][0] = fa; dep[u] = dep[fa] + 1;

    for(int i = head[u]; i; i = e[i].next)

       if(e[i].to != fa)

         getDF(e[i].to, u);

}

int LCA(int u, int v){

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

    int cha = dep[u] - dep[v];

    if(cha)

      for(int i = 0; i <= 18; ++i)

         if((cha >> i) & 1)

           u = f[u][i];

    if(u != v){

      for(int i = 18; ~i; --i)

         if(f[u][i] != f[v][i])

           u = f[u][i], v = f[v][i];

      return f[u][0];

    }

    return u;

}

int dis(int u, int v){

    return dep[u] + dep[v] - (dep[LCA(u, v)] << 1) + 1;

}

void print(int x){

    if(x > 1) print(x >> 1);

    printf("%d", x & 1);

}

int main(){

    n = read(); m = read();

    for(int i = 1; i <= m; ++i)

       Add(read(), read());

    for(int i = 1; i <= n; ++i)

       if(!dfn[i])

         Tarjan(i, 0);

    memset(head, 0, sizeof head);

    int tmp = num;

    for(int i = 2; i <= tmp; i += 2)

       if(belong[e[i].from] != belong[e[i].to])

         Add(belong[e[i].from], belong[e[i].to]);

    getDF(1, 0);

    for(int j = 1; j <= 18; ++j)

       for(int i = 1; i <= dcc; ++i)

          f[i][j] = f[f[i][j - 1]][j - 1];

    t = read();

    while(t--) print(dis(belong[read()], belong[read()])), puts("");

    return 0;

}

巴特西

【洛谷 P2783】有机化学之神偶尔会做作弊（双联通分量）

最新文章

热门文章

巴特西

【洛谷 P2783】 有机化学之神偶尔会做作弊 （双联通分量）

最新文章

热门文章

【洛谷 P2783】有机化学之神偶尔会做作弊（双联通分量）